Файл: Tannenbaum.pdf

3 6 8 Глава 5. Уровень архитектуры команд

В машине IJVM при доступе к локальной переменной используется указатель

ячейки памяти (LV) в регистре плюс небольшое смещение в самой команде, как

показано на рис. 4.14,

 а.

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

и небольшое смещение в регистре. Чтобы показать, как это работает, рассмот-

рим следующий пример. У нас есть два одномерных массива А и В по 1024 слова
в каждом. Нам нужно вычислить А, И Bi для всех пар, а затем соединить все эти

1024 логических произведения операцией ИЛИ, чтобы узнать, есть ли в этом на-

боре хотя бы одна пара, не равная нулю. Один из вариантов — поместить адрес

массива А в один регистр, а адрес массива В — в другой регистр, а затем последова-

тельно перебирать элементы массивов, аналогично тому, как мы делали в преды-

дущей программе (см. листинг 5.1). Такая программа, конечно же, будет работать,

но ее можно усовершенствовать, как показано в листинге 5.2.

Л и с т и н г  5 . 2 .

  П р о г р а м м а  н а языке  а с с е м б л е р а для вычисления  о п е р а ц и и  И Л И  о т

(Ai И Bi) для  м а с с и в а из 1024 элементов

MOV Rl,#0 ;собирает результаты выполнения ИЛИ в R1.
MOV R2.#0 :R2=

 л

 от текущего произведения  A [ i ] И  B [ i ]

MOV R3.#4096 ;R3=nepBoe ненужное значение индекса

LOOP: MOV R4.A(R2) ;R4-A[i]

AND R4,B(R2) ;R4=A[l] И  B [ i ]
OR R1.R4

ADO R2.#4 И-1+4

CMP R2.R3 ;нужно ли продолжать?
BLT LOOP ;если R2<R3, мы не закончили и нужно продолжать

Здесь нам требуется 4 регистра:

1. R1 — содержит результаты суммирования логических произведений.

2. R2 — индекс i, который используется для перебора элементов массива.

3. R3 — константа 4096. Это самое маленькое значение i, которое не используется.

4. R4 — временный регистр для хранения каждого произведения.

После инициализации регистров мы входим в цикл из шести команд. Команда

напротив LOOP вызывает элемент Ai в регистр R4. При вычислении источника здесь
используется индексная адресация. Регистр (R2) и константа (адрес элемента А)

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

Сумма этих двух величин поступает в память, но не сохраняется ни в одном из
видимых пользователем регистров. Запись

MOV R4.ACR2)

означает, что для определения пункта назначения используется регистровая

адресация, где R4 — это регистр, а для определения источника используется ин-
дексная адресация, где А — это смещение, a R2 — это регистр. Если А имеет значе-

ние, скажем, 124300, то соответствующая машинная команда будет выглядеть так,
как показано на рис. 5.13.

MOV

R4

R2

124300

Рис.

 5.13. Возможное представление команды MOV R4, A{R2)

Адресация 369

Во время первого прохождения цикла регистр R2 принимает значение 0 (по-

скольку регистр инициализируется таким образом), поэтому нужное нам слово АО
находится в ячейке с адресом 124300. Это слово загружается в регистр R4. При
следующем прохождении цикла R2 принимает значение 4, поэтому нужное нам
слово А1 находится в ячейке с адресом 124304 и т. д.

Как мы говорили раньше, здесь смещение — это указатель ячейки памяти, а значе-

ние регистра — это небольшое целое число, которое во время вычисления меняется.
Такая форма требует, чтобы поле смещения в команде было достаточно большим

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

Относительная индексная адресация

В некоторых машинах применяется способ адресации, при котором адрес вычис-

ляется путем суммирования значений двух регистров и смещения (смещение фа-
культативно). Такой подход называется

 относительной индексной адресацией.

Один из регистров — это база, а другой — это индекс. Такая адресация очень удоб-
на при следующей ситуации. Вне цикла мы могли бы поместить адрес элемента А
в регистр R5, а адрес элемента В в регистр R6. Тогда мы могли бы заменить две
первые команды цикла LOOP на

LOOP: MOV R4,(R2+R5)

AND R4,(R2+R6)

Было бы идеально, если бы существовал способ адресации по сумме двух регист-

ров без смещения. С другой стороны, даже команда с 8-битным смещением была
бы большим достижением, поскольку мы оба смещения могли бы установить на 0.
Однако если смещения всегда составляют 32 бита, тогда мы ничего не выиграем,

используя такую адресацию. На практике машины с такой адресацией обычно
имеют форму с 8-битным и 16-битным смещением.

Стековая адресация

Мы уже говорили, что очень желательно сделать машинные команды как можно
короче. Конечный предел в сокращении длины адреса — это команды без адресов.
Как мы видели в главе 4, безадресные команды, например IADD, возможны при
наличии стека. В этом разделе мы рассмотрим стековую адресацию более подробно.

Обратная польская запись

В математике существует древняя традиция помещать оператор между операнда-
ми (х+у), а не после операндов (ху+). Форма с оператором между операндами на-
зывается

 инфиксной записью.

 Форма с оператором после операндов называется

постфиксной

 или

 обратной польской записью

 в честь польского логика Я. Лука-

севича (1958), который изучал свойства этой записи.

Обратная польская запись имеет ряд преимуществ над инфиксной записью

 для

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

3 7 0 Глава 5. Уровень архитектуры команд

стеками. В-третьих, инфиксные операторы имеют приоритеты, которые произволь-
ны и нежелательны. Например, мы знаем, что axb+c значит (axb)+c, а не ах(Ь+с),
поскольку произвольно было определено, что умножение имеет приоритет над
сложением. Но имеет ли приоритет сдвиг влево над логической операцией И? Кто
знает? Обратная польская запись устраняет такие недоразумения.

Существует несколько алгоритмов для превращения инфиксных формул в об-

ратную польскую запись. Ниже изложена переделка идеи Э. Дейкстры. Предполо-
жим, что формула состоит из следующих символов: переменных, двухоперандных
операторов +, -, *, /, а также левой и правой скобок. Чтобы отметить конец форму-
лы, мы будем вставлять символ -L после последнего символа одной формулы и пе-
ред первым символом следующей формулы.

Калифорния

А

X

-

(

-

В - +

- С

J- )

4-

О  О О  О О ^ О О ^  О О

0 0 О О

Нью-Йорк

Железнодорожная

стрелка

Техас

Рис. 5.14. Каждый вагон представляет собой один символ в формуле, которую нужно

переделать из инфиксной формы в обратную польскую запись

На рис. 5.14 нарисована железная дорога из Нью-Йорка в Калифорнию с раз-

вилкой, ведущей в Техас. Каждый символ формулы представлен одним вагоном.

Поезд движется на запад (налево). Перед развилкой каждый вагон должен останав-

ливаться и узнавать, должен ли он двигаться прямо в Калифорнию, или ему нужно

по пути заехать в Техас. Вагоны, содержащие переменные, всегда направляются

Калифорнию и никогда не едут в Техас. Вагоны, содержащие все прочие символы,

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

отправившегося в Техас.

В таблице на рис. 5.15 показана зависимость ситуации от того, какой вагон от-

правился последним в Техас и какой вагон находится у развилки. Первый 1 всегда

отправляется в Техас. Числа соответствуют следующим ситуациям:

1. Вагон на развилке направляется в Техас.

2. Последний вагон, направившийся в Техас, разворачивается и направляется

в Калифорнию.

3. Вагон, находящийся на развилке, и последний вагон, отправившийся в Техас,

угоняются и исчезают (то есть оба удаляются).

Адресация

371

4. Остановка. Символы, находящиеся в Калифорнии, представляют собой фор-

мулу в обратной польской записи, если читать слева направо.

5. Остановка. Произошла ошибка. Изначальная формула была некорректно

сбалансирована.

Вагон на развилке

1 + Р х / ( )

4

2

2

2

2

5

1

2

2

2

2

1

1

2

2

2

2

1

1

1

1

2

2

1

1

1

1

2

2

1

1

1

1

1

1

1

5

2

2

2

2

3

Рис. 5.15.

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

После каждого действия производится новое сравнение вагона, находящегося

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

Таблица 5.5.

 Некоторые примеры инфиксных выражений и их эквиваленты

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

Инфиксная запись

Обратная польская запись

А+ВхС
АхВ+С
AxB+CxD

(A+B)/(C-D)

АхВ/С

((А+В) xC+D)/(E+F+G)

А В С х +
АВхС+
А Вх С Dx+
А В+С D-/
А В х С /
A B+CxD+ E F + G +/

Порядок переменных в инфиксной и обратной польской записи одинаков. Одна-

ко порядок операторов не всегда один и тот же. В обратной польской записи опера-
торы появляются в том порядке, в котором они будут выполняться. В табл. 5.5

даны примеры инфиксных формул и их эквивалентов в обратной польской записи.

Вычисление формул в обратной польской записи

Обратная польская запись — идеальная запись для вычисления формул на компью-
тере со стеком. Формула состоит из п символов, каждый из которых является
или операндом, или оператором. Алгоритм для вычисления формулы в обратной

3 7 2 Глава 5. Уровень архитектуры команд

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

В таблице 5.6 показано вычисление выражения
(8+2x5)/(1+3x2-4)

в машине JVM. Соответствующая формула в обратной польской записи выглядит
следующим образом:

825х+132х+4-/
В таблице мы ввели команды умножения и деления IMUL и IDIV. Число на верши-

не стека — это правый операнд (а не левый). Это очень важно для операций деле-
ния и вычитания, поскольку порядок операндов в данном случае имеет значение
(в отличие от операций сложения и умножения). Другими словами, команда I0IV
определяется следующим образом: сначала в стек помещается числитель, потом
знаменатель, и тогда выполнение операции дает правильный результат. Отметим,
что преобразовать обратную польскую запись в код (I)JVM очень легко: нужно
просто просканировать формулу в обратной польской записи и выдавать одну ко-
манду с каждым символом. Если символ является константой или переменной,
нужно выдавать команду помещения этой константы или переменной в стек. Если

символ является оператором, нужно выдавать команду для выполнения данной
операции.

Способы адресации для команд перехода

До сих пор мы рассматривали только те команды, которые оперируют с данными.

Командам перехода (а также командам вызова процедур) также нужны особые

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

Другие способы адресации тоже имеют смысл. Косвенная регистровая адреса-

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

Индексная адресация, при которой известно смещение от регистра, также яв-

ляется вполне разумным способом. Этот способ обладает теми же свойствами, что
и косвенная регистровая адресация.

Еще один вариант — относительная адресация по счетчику команд. В данном

случае для получения целевого адреса смещение (со знаком), находящееся в самой
команде, прибавляется к программному счетчику. По сути, это индексная адреса-
ция, где в качестве регистра используется PC.