Нельзя просто так взять и обойтись без переноса

Если нельзя, но очень хочется, то можно все равно нельзя

Продолжая работу по изучению архитектуры RISC-V, обратил внимание на один аспект данного направления, существенно отличающий приборы данного типа от архитектур, с которыми я привык работать, а именно отсутствие слова состояния признаков (СС). Данный пост и освещает вопрос о том, что такое перенос, для чего он нужен, где может храниться и можно ли без него обойтись (спойлер — нельзя).

Те, кому данная тема интересна, могут нажать на кнопку.

Итак, мы начинаем.

Часть 1. Необходимое вступление

Слово состояний (СС) процессора — это некое особым образом организованное аппаратное решение, предназначенное для хранения текущей информации о результатах некоторых ранее выполненных операций. Доступ к нему может производиться как с помощью специальных операций, так и отображением на адресное пространство регистров или даже памяти. Данный аспект реализации не является определяющим, поскольку в основном к содержанию слова состояния мы обращаемся не напрямую, а в используем его в контексте выполняемых команд.

Значение имеет состав данных, в слове состояний хранящийся и ключевым для дальнейшего рассмотрения будет набор признаков результата, в любимой мною архитектуре DEC это NZVC. Примечание на полях (Пнп): любые совпадения обозначений данных признаков с надписями на футболках отдельных одиозных личностей, считающих себя телеведущими, а также иных арт-объектов, являются случайными и обусловлены исторически. Все эти признаки описывают результаты некоей ранее выполненной операции, не обязательно непосредственно предшествующей команде, в которой они анализируются (используются).
N – признак отрицательности результата этой операции (старший разряд равен 1), Z – признак нулевого результата (все биты, включая знаковый, равны нулю), V – признак знакового переполнения (комбинация значений остальных признаков), C – признак переноса (результат операции не умещается в разрядной сетке). Кроме этих признаков, обычно представленных в виде отдельных битов СС, последнее может содержать и дополнительную информацию о режиме выполнения текущей команды — бит трассировки T, поле режима исполнения (Thumb), уровень привилегий(usr|core), состояние разрешения обработки прерываний и текущий уровень обработки, а также другие специфичные для архитектуры данные, которые все равно надо где-то хранить, так почему бы и не в СС. Далее мы сосредоточимся только на признаках, поскольку на все остальные поля никто не посягает и проблема не в них.

Как правило, значения признаков N и Z используются для организации управления последовательностью выполнения команд при помощи команд условного перехода или условного исполнения команд. Существуют два различных набора команд ветвления для различной интерпретации типов данных — знаковых и без-знаковых. Для первого типа это BGE, BGT, BLT, BLE, для второго BHIS, BHI, BLO, BLOS, ну а ветвление BEQ и BNE одинаковы для любых типов. Признак V фиксирует факт переполнения в результате выполнения арифметических операций и позволяет организовать переход на программу обработки исключений командами типа BVS/BVC. В некоторых архитектурах данные признаки формируются автоматически при выполнении арифметических команд, в некоторых существует отдельная команда TST, позволяющая сформировать эти признаки для содержания конкретного регистра, хранящего результат предыдущей операции.

А вот с признаком С несколько сложнее. Во-первых, этот признак фиксирует наличие переноса при выполнении арифметических операций и в таком качестве может быть использован как для формирования переходов BCS/BCC, так и в качестве неявного (дополнительного) операнда в арифметических операциях с длинными числами (ADDC вместо ADD). Во-вторых, он также может использоваться, как дополнительный бит-приемник/источник в операциях «длинного» и циклического сдвигов. А в-третьих, далеко не все команды изменения данных влияют на бит С, и для этого есть веские основания, связанные с организацией обработки длинных данных.

Часть 2

Формулируем задачу и решаем

А теперь, когда мы установили состав слова состояния, попробуем без него обойтись и начнем с относительно простых вещей.

Пнп: на самом деле мы пробуем исключить из СС только признаки результата, на прочие поля мы на посягаем. Связано данное желание с тем, что формирование признаков в процессе выполнения команд обработки сильно затрудняет нам возможность изменение порядка выполнения команд в процессе исполнения кода (re-ordering).

Признаки N и Z – первоочередные кандидаты на исключение, поскольку они просто дублируют состояние некоторых битов данных. Первый — это просто алиас для старшего битового разряда, да и второй не сложен в реализации (сумма по И всех битов слова). Можно просто объединить команду тестирования содержимого регистра и формирования перехода, но в рассматриваемой архитектуре пошли чуть дальше — объединили команду сравнения двух данных (часто в качестве одного из них используют ноль) и команду перехода с разными условиями в одно целое. Получается вполне себе элегантное решение:

if (Data<=0) … превратится в
BLE r0,r1,L1
(что эквивалентно последовательности)
TST r1 (CMP r1,#0)
BLE L1

которое позволяет даже уменьшить код программы на 1 слово. Да, Вам потребуется длинное слово для кодирования команды, но оно у нас уже есть (32 бита или 16 для режима сжатия).
Ситуация с признаком V точно такая же, так что здесь проблем так же не предвидится.

А вот с битом C проблемы точно есть и прежде всего рассмотрим сдвиг длинного слова, здесь нам надо переносить старший (младший) бит из одного слова в другое и где-то его сохранять между операциями. Конечно, есть простое и естественное решение — вначале спрятать куда-то (наверное, в младший бит промежуточного регистра) переносимый бит слова, затем сдвинуть собственно слово, потом сдвинуть второе слово и вернуть спрятанный бит в старший (младший бит) слова результата.

Но, когда нам потребуется сдвиг длинного данного более, чем на 1 разряд, многократное повторение вышеуказанной процедуры становится утомительным. И здесь разработчики архитектуры нашли «воистину замечательное решение», которое лучше всего проиллюстрировать примером реализации сдвига влево на 12 разрядов двойного слова данных в паре (r2.r1):

rsr r3,r1,#32-12 ; младшие 12 разрядов старшего слова результата
rsl r1,r1,#12 ; младшее слово результата
rsl r2,r2,#12 ; старшие 20 разрядов старшего слова результата
or r2,r3,r2 ; собственно старшее слово результата.

Если учесть возможность использования специального регистра в качестве счетчика для длинного сдвига слова (в предыдущих командах сдвиг выполнялся на константное количество бит) и особенности проведения операций сдвигов в разные стороны — сдвиг влево идет на значение счетчика, а сдвиг вправо — на (32-значение счетчика), то операция сдвига длинного слова на произвольное значение разрядов становится совсем простой и осуществляется без перезагрузки значения счетчика сдвига за счет разной интерпретации содержимого регистра.
Так что со сдвигами длинных слов мы справились, причем бит переноса вообще не потребовался.

Есть еще одно интересное применение бита С — выдвижение в него очередного бита (старшего либо младшего) для передачи одновременно со сдвигом собственно слова данных для передачи. Данный трюк постоянно использовался в программах на ассемблере, но на языке С не имеет естественной реализации. Его можно проимитировать при помощи очевидной последовательности команд

int tmp = data & 0x01; 
data = data >>1; 
if (tmp) …. 

но никаких проблем с трансляцией данного фрагмента у компилятора для RISC-V не будет, поскольку здесь бита С нет, а есть лишь его имитация. Да, имитация не очень удачная, но тут уже претензии не к архитектуре без переноса, а к конкретному языку программирования.

Со сдвигами вроде разобрались, но со сложением так просто не получится, поскольку перенос из младшего слова реально надо учитывать при операции со старшим словом данных и обойтись без него нельзя, от слова «совсем». Пнп: в интересной книге «Хаки для программистов» есть раздел, посвященный длинной арифметике, в начале которого нам обещают показать, как проводить операции без переноса, а потом дают псевдокод такого метода. В первой строке складывают младшие слова, а в следующей при помощи набора логических операций формируют объект, называемый С, который и суммируют со старшими словами. Раз уж «хакеры» с задачей избавится от переноса не справились, что же говорить о нормальных программистах.

Естественным решением выглядит использование некоторого регистра (его младшего бита) для хранения значения переноса от его создания до использования. Но если мы будем использовать заранее определенный регистр, исходная проблема сохранится, и мы не сможем изменить порядок команд, формирующих этот бит, не рискуя потерять значения в нем до их использования. Значит, нам потребуется много места для битов переноса, и обычные регистры предоставят нам это место. Тогда номер регистра хранения переноса мы можем просто указать в команде, производящей операцию, как дополнительный параметр — вполне приемлемое решение. При таком подходе фрагмент кода
register uint64_t lg, lr; lr=lg+1; // r4.r3 < — r2.r1+1
который в случае «нормальной» архитектуры с переносом превратился бы в 2 команды ассемблера:

addi r3,r1,#1;
addc r4,r2,#0

обзаведется дополнительной командой и потребует дополнительного регистра:

addi r3,r1,#1; инкрементируем младшую часть
sltu r4,r3,r1; формируем бит переноса, анализируя операнд и результат
add r4,r3,r4; прибавляем перенос к старшей части

Прибавилась 1 команда для формирования переноса. Не уверен, что такой overhead (50%) компенсируется возможностью переставить команды (тем более, что в данном случае ничего и не переставляем), но уже для переменной из памяти ситуация не столь катастрофична -для реализации следующей операции uint64_t lg; lg++; вместо 6 команд (чтение длинной переменной в регистры — 2 команды, собственно операция — 2 команды, запись в память — 2 команды) потребуется лишь 7 команд (чтение 2 команды, операция (2+1)=3 команды, запись 2 команды), что приводит к лишней одной команде, или увеличению на 16%. Для сложения двух длинных слов вместо 4+2+2=8 потребуется 4+3+2=9, что тоже не слишком много.
В любом случае, не думаю, чтобы разработчики архитектуры RISCV (и MIPS заодно и, вроде как, SPARC) не взвесили все аспекты подобного решения. Пнп: мое личное мнение, ни в коей мере никому не навязываемое и не подкрепленное расчетами или практикой разработки АЛУ, состоит в том, что отсутствие слова признаков все-таки более фича, нежели реальная необходимость, что подтверждается практикой ARM (и x86 заодно), читатели могут высказать свое мнение в опросе.

Осталось понять, что делает команда SLTU – понятно, что формируется перенос, но как, Холмс? Сначала я предположил, что анализируются знаки результата и операнда, но не сходилось. Тогда посмотрел описание системы команд и обнаружил, что это просто акроним от Set Less Then (Unsigned) и это команда сравнения двух операндов, которая формирует значение 1 в регистре результата, если первый операнд меньше второго, ничего экстраординарного. Сразу ясно применение этой команды в операции сложения и вот пример сложения двух длинных чисел (пары (r1.r0) и пары (r3.r2), результат в паре (r5.r4)), чтобы увидеть обработку переноса:

add r4,r2,r0; сложили младшие части
sltu r5,r4,r2; установили r5 в 1, если результат меньше слагаемого
add r5,r5,r1; прибавляем перенос к старшей части слагаемого
add r5,r5,r3; прибавляем старшую часть второго слагаемого.

Возникает вопрос, а почему нужна именно команда установки бита в регистре, ведь прекрасно можно обойтись обычными командами сравнения и перехода. Здесь ответ очевиден — переход не самая удачная идея, поскольку не слишком хорошо сочетается с конвейером. Но есть еще и вариант с условным исполнением команд, и он вполне приемлем, хотя и хуже с точки зрения возможной векторизации. Тем не менее сделано то, что сделано.

Со сложением все очевидно и понятно, но для вычитания такой подход не сработает. Пнп: перенос/заём формируется несколько по-разному для сложения и вычитания. Приведу следующий пример: исходное число 2 — 0х02, прибавляем к нему 254 — 0хFE, получаем 256 — 0х00 и бит С должен быть сформирован. Теперь от числа 2 отнимем 2 (прибавим 0xFE — дополнение двух), результат по-прежнему 0, но заёма быть не должно.
Рассматриваем код вычитания длинных чисел (пары (r1.r0) из пары (r3.r2) с результатом в (r5.r4)), и ожидаем увидеть команду, противоположную к SLTU (SGTU ?), чтобы получить правильное значение заёма, но видим по-прежнему именно ее:

sub r4,r2,r0; вычитаем младшие части
sltu r5,r2,r4; формируем заем
sub r5,r3,r5; вычитаем из старшей части заем
sub r5,r5,r1; вычитаем из старшей части вычитаемое.

Ответ кроется в деталях применения — в команде sltu изменен порядок операндов и заём формируется, если результат больше, чем уменьшаемое, что совершенно логично.

Теперь рассмотрим еще один интересный случай, привлекший мое внимание, а именно декремент длинного слова:

addi r2,r0,#-1 ; декремент младшего слова
sltu r4,r2,r0 ; формирование переноса как при сложении
addi r3,r1,#-1 ; хитрый трюк
add r3,a3,r4 ; прибавление переноса к старшей части.

Секрет спрятан в команде 3, которая, по сути, инвертирует значение переноса, выполнив предварительную операцию вычитания 1 из старшего слова.

Почему данный фрагмент меня заинтересовал — потому что фрагмент ниже, придуманный мною и аналогичный варианту с вычитанием, выполняет ту же операцию и занимает на одну команду меньше:

addi r2,r0,#-1 ; декремент младшего слова
sltu r4,r0,r2 ; формирование заема
sub r3,a1,r4 ; вычитание заема из старшей части.

Хотя, может быть, вычитание более дорогая операция по времени, но вряд ли она займет место двух сложений, так что почему компилятор создает первый вариант, я ответить не смогу. Если среди моих читателей есть разработчики компилятора GCC, буду благодарен за разъяснения.

Общий вывод — отказаться от бита переноса в слове состояний можно, отказаться от использования переноса вообще нельзя.