2.19. Обмен содержимого регистров

Существует стЕфый, хорошо известный способ обмена содержимым двух регистров без использования третьего [34].

xi-хФу у*-уФх ххФу

Этот метод хорошо работает на двухадресной машине. Он остается работоспособным и при замене оператора Ф дополнительным к нему оператором эквивалентности з. Возможно также использование различных наборов операций сложения и вычитания.

xi-x + y х<г-х-у Xi-y-X у<х-у у<у + х у<у-х х*-х-у х*-у-х х<-х + у

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

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

Вне цикла: 1*-хФу Внутри цикла: ж <- ж Ф t у <-уФг

Обмен соответствующих полей регистров

Зачастую требуется обменять биты двух регистров хиу, если i-й бит маски »1,=1, и оставить их неизменными, если 1Я/=0. Под обменом "соответствующими" полями подразумевается обмен без сдвигов. В маске m единичные биты не обязательно должны быть смежными. Приведем простейший метод решения поставленной задачи.

x«-(x&m)(y&m) у «-(у&т)(х&я) х<-х

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

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

(а) (б) (в)

х«-хФу х«-х = у Г<-(хФу)&т

у<-уФ(х&т) у«-у=(хт) х«-хФ/

Х<-хФу X*-Xsy ууф1

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

Метод из столбца (в) предложен в [19]. Он тоже требует выполнения пяти команд (в предположении, что для загрузки т в регистр используется одна команда), но на машинах с достаточными возможностями распараллеливания вычислений на уровне команд выполнейие этого кода занимает всего три такта.

Обмен двух полей одного регистра

Предположим, что в регистре х необходимо поменять два поля (одинаковой длины), не изменяя при этом прочие биты регистра - т.е. нам требуется поменять местами поля В и D в пределах одного машинного слова, не изменяя при этом содержимое полей Л, С и Е. Поля расположены друг от друга на расстоянии k бит.

Следующий код сдвигает поля D и В на новые позиции и затем комбинирует полученные слова с помощью команд и и ши.

Г,=(лг&1я)<кЛ

&т

Здесь маска т содержит единичные биты в поле D (и нулевые биты в других полях), а маска т содержит единичные биты в полях Л, С и £. На машине с неограниченными возможностями распараллеливания вычислений на уровне команд требуется выполнение девяти команд за четыре такта, так как для загрузки двух масок необходимо выполнить две команды.

Ниже описан метод обмена полями [19], который в тех же предположениях требует выполнения семи команд и выполняется за пять тактов. Он аналогичен алгоритму обмена соответствующими полями двух регистров, описанному ранее в подразделе "Обмен соответствующих полей регистров" в столбце (в). Здесь, как и ранее, т - маска, выделяющая поле D.

&т

Идея состоит в том, что ti в позициях поля D содержит биты В ® D (и нули в остальных полях), а t2 содержит биты B®D в поле В. Этот код, как и приведенный ранее, работает корректно, даже если В uD представляют собой поля, разбитые на части, т.е. даже если в маске т единичные биты не являются смежными.

Условный обмен

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

лись корректно установленные единичные биты при выполнении условия с. Если формирование маски т выполняется без команд ветвления, код условного обмена также не будет содержать этих команд.

2.20. Выбор среди двух или большего количества значений

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

Вот простейший код переключения:

if (X == а) х = Ь; else X = а;

А это его эквивалент в языке С: X = (X == а) ? b : а,-

* Однако существенно лучше (по крайней мере эффективнее) использовать другой способ: х<-а+Ь-х или X<-аФЬФX . Если а и b - константы, то вычисления требуют всего одной или двух команд из базового множества RISC-команд. Естественно, переполнение при вычислении а+Ь можно игнорировать.

Возникает закономерный вопрос: существует ли эффективный метод циклического перебора трех и более значений? Иными словами, пусть заданы три произвольные, не равные друг другу константы а, b ис. Требуется найти легко вычисляемую функцию /, которая удовлетворяет условиям

f{a) = b; f{b) = c; f{c) = a.

Любопытно отметить, что всегда существует полиномиальная функция, удовлетворяющая указанным условиям. В случае трех констант это функция

{х-а){х-Ь) {х-Ь){х-с) {х-с){х-а) > {с-а){с-Ь) {а-Ь){а-с) {b-c){b-a)

Идея заключается в том, что при х = а первый и последний члены функции обращаются в нуль и остается только средний член при коэффициенте b и т.д. Для вычисления этой функщ1И необходимо выполнить 14 арифметических операций, при этом в общем случае промежуточные результаты превышают размер машинного слова, хотя мы имеем дело всего лишь с квадратичной функцией. Однако если для вычисления полинома применить схему Горнера, то понадобится выполнить только пять арифметических операций (четыре для вычисления квадратов с целыми коэффициентами и заключительное деление). После преобразований (2) получим следующий вид функции:

Правило Горнера состоит в вынесении х за скобки. Например, полином четвертой степени ax*+bx+cx+dx+e вычисляется как x{x{x{ax+b}+c)+d)+e . Для вычисления полинома степени п требуется п умножений и п сложений; при этом наличие команды умножения со сложением существенно повышает эффективность вычислений.