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

Формулы, в которых используется функция "nlz", взяты из [56]. Ее использование позволяет вычислить результат отношения ж = у в виде 1 или О всего за три команды.

nlz(jc-y)3>5

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

х=0: abs(jc)-l

abs(x +0x80000000)

nlz(x)<K26

nlz(x)3>5

-.{x\-x) -*&(x-l) хфО: nabs(x)

nlz(x)-32 x\-x

x»lj-x [10]

x<0: X x<Q: x\{x-\) xb-x x>Q: x®nabs(x)

(xil)-x x>0: -Л

Знаковое сравнение можно получить из беззнакового, увеличивая сравниваемые величины на 2. Обратное преобразование также справедливо. Таким образом получаем

х<у = х + 2"<у + 2, х<у = х-2" <у-2" .

Аналогичные соотношения выполняются для < и т.д. В данном случае прибавление и вычитание числа 2 - эквивалентные действия, так как обе операции инвертируют значение знакового разряда.

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

ау имеют одинаковые знаки, то х <у = х<у ,а если их знаки различны, то х<у = х>у [42]. В этом случае также справедливы обратные преобразования; таким образом, получаем

х<у =

х<у

ФдГз.Фуз,,

Ж<у = (ж<у)ФЖз,ФУз,,

где х,у и Уз, представляют собой знаковые биты хиу соответственно. Аналогичные выражения получаются для отношений <, < и других.

Применение описанных способов позволяет вычислить все стандартные команды сравнения (кроме = и 5t) через другие команды сравнения с использованием не более трех дополнительных команд на большинстве машин. Например, возьмем в качестве исходной команды сравнения отношение хку , поскольку реализовать его проще других команд (как бит переноса у-х). Тогда остальные команды сравнения можно реализовать следующим образом:

-,y+2"x + 2"j

x + 2"Sy + 2" х + 2"у+2"

х<у хйу х>у х>у х<у

х>у хку

= у + 2"кх + 2" укх

х<у

Команды сравнения и бит переноса

Если процессор может легко поместить бит переноса в регистр общего назначения, то для некоторых операций отношения это позволяет получить очень лаконичный код. Ниже приводятся выражения такого рода для некоторых отношений. Запись сапу {выражение) означает, что разряд переноса генерируется при выполнении команды выражение. Предполагается, что бит переноса для разности х-у тот же, что и на выходе сумматора для выражения х + у +1, и является дополне!Нием "заема".

сапу(0-(х-у)), или

сапу((х + у) + 1), или

сапу((х-у-1) + 1)

сапу ((х - у) -1) = сапу ((х - у) + (-1))

-псапу((х + 2)-(у + 2"))

х = у;

х*у: х<у .

2.U. ПРЕДИКАТЫ СРАВНЕНИЯ

xiy: carry((y+2")-(x + 2"))

x<y:

-.carry (jc-jr) xky: cmy{y-x) x=0: cany(0-Jc), или carry(jc+l)

хф9: carry ( jc-1) = сапу (jc+ (-!))

x<0: carry(x + x)

XSO: cany(2"-(x + 2"))

Для X > у используется дополнение выражения для х < у ; то же справедливо и для других типов отношения "больше".

При вычислении условных выражений на ЮМ RS/6000 и близком к нему PowerPC была использована программа GNU Superoptimizer [17]. У RS/6000 имеются команды abs(x), nabs(x), doz(x,y) и ряд различных команд сложения и вычитания с использованием переноса. Как выяснилось, RS/6000 может вычислить все целочисленные условные выражения с помощью не более чем трех элементарных (выполняющихся за один такт) команд - результат, удививший даже самих создателей машины. В состав "всех условных выражений" входят шесть команд знакового сравнения и четыре команды беззнакового сравнения, а также их версии, в которых второй операнд равен нулю (при этом каждая из команд имеет два варианта - возвращающий результат 1/0 и возвращающий результат -1/0). Power PC, где нет функций abs(x), nabs(x) и doz(x,y), вычисляет все

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

Вычисление отношений

Большинство компьютеров возвращают однобитовый результат операции сравнения, который обычно размещается в "регистре условий", а на некоторых машинах (как, например, в нашей RISC-модели) - в регистре общего назначения. В любом случае вычисление отношений зачастую реализуется вычитанием операндов и некоторыми действиями над битами полученного результата, чтобы получить окончательный однобитовый результат работы команды сравнения.

Рассмотрим логику описанных выше действий. Пусть вместо разности х-у компью-

тф вычисляет сумму х + у +1, ив результате этих вычислений получаются следующие величины:

Со - перенос из старшего разряда в разряд переноса; С, - перенос в старший разряд;

- бит знака результата; Z - величина, равная 1, если полученный результат (за исключением Со) нуле вой, и О в противоположном случае.

Таким образом, в системе обозначений булевой алгебры для различных отношений получим приведенные ниже выражения (расположение рядом двух величин подразумевает операцию и, а оператор "+" означает операцию или).