Файл: Tannenbaum.pdf

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

чтобы избежать проблем с вводом-выводом Java. Единственное различие — это за-
мена оператора Java printf на стандартный оператор языка С

printfC"Переместить диск с

 %6

 на

 %d\r\",

 i,j)

Синтаксис строки printf не важен (строка печатается буквально за исключе-

нием *d — это означает, что следующее целое число будет дано в десятичной сис-
теме счисления). Здесь важно только то, что процедура вызывается с тремя пара-
метрами: форматирующей строкой и двумя целыми числами.

Мы использовали язык С для Pentium II и UltraSPARC II, поскольку библио-

тека ввода-вывода Java не доступна для этих машин, а библиотека С доступна.
Для JVM мы будем использовать язык Java. Разница минимальна: всего один опе-
ратор вывода строки на экран.

Решение задачи «Ханойская башня»

на ассемблере Pentium II

В листинге 5.7 приведен возможный вариант трансляции программы на языке С

для компьютера Pentium П. Регистр ЕВР используется в качестве указателя фрей-
ма. Первые два слова применяются для установления связи, поэтому первый па-
раметр п (или N, поскольку регистр для макроассемблера не важен) находится в
ячейке ЕВР+8, а за ним следуют параметры i и j в ячейках ЕВР+12 и ЕВР+16 соот-
ветственно. Локальная переменная к находится в ЕВР+20.

Листинг 5.7.

 Решение задачи «Ханойская башня» для машины Pentium II

.586 ;компилируется для Pentium

.MODEL FLAT

PUBLIC _towers ;экспорт 'towers'

EXTERN _printf:NEAR ;импорт printf

.CODE

_towers: PUSH EBP сохраняет ЕВР (указатель фрейма)

MOV EBP. ESP [устанавливает новый указатель фрейма над ESP

CMP[EBP+8].l ;if(n==l)

JNE LI ;переход, если п?1

MOV EAX. [EBP+16] ;printf("...". i. j);

PUSH EAX ;сохранение параметров i. j и формата

MOV EAX. [ЕВР+12] ;строка помещается в стек

PUSH EAX ;в обратном порядке. Таково требование языка С

PUSH OFFSET FLAT:format : OFFSET FLAT - это адрес формата

CALL _printf ;вызов процедуры printf

ADD ESP. 12 :удаление параметров из стека

JMP Done ;завершение

MOV EAX.6 ;начало вычисления k=6-i-j

SUB EAX. [EBP+12] :EAX=6-i

SUB EAX. [EBP+16] ;EAX-6-i-j

MOV [EBP+20], EAX ;k=EAX

PUSH EAX ;начало процедуры towers(n-l, п. к)

MOV EAX. [EBP+12] ;EAX=i

PUSH EAX ;помещает в стек i

MOV EAX. [EBP+8] ;EAX=n

DEC EAX;EAX=n-l

PUSH EAX ;помещает в стек n-1

CALL _towers ;вызов процедуры towers(n-1. i, 6-i-j)

Ханойская башня 419

Done:

.DATA

format

END

ADD ESP.

MOV EAX.

PUSH EAX

MOV EAX,

PUSH EAX

PUSH 1

12

[EBP+16]

[EBP+12]

CALL towers
ADD ESP.

MOV EAX.

PUSH EAX

MOV EAX,

PUSH EAX

MOV EAX.

DEC EAX:!

PUSH EAX

12

[EBP+12]

[EBP+20]

[EBP+8]

ГАХ-n-l

CALL towers

ADD ESP.

LEAVE

RET 0

12

DB "Переместить диск

:удаление параметров из стека

тачало процедуры towers (1, i, j)

:помещает в стек j

:EAX=i

:помещает в стек i

шомещает в стек 1

;вызывает процедуру towersCl, t, j)
:удаляет параметры из стека

.•начало процедуры towers(n-l. 6-i-j. i)

.•помещает в стек i

:EAX=k

:помещает в стек к

:ЕАХ = п

;помещает в стек п-1

:вызов процедуры towersСn-1, 6-i-j. i)
:корректировка указателя стека

;под готовка к выходу

.•возврат к вызывающей программе

с

 %d

 на

 £d\n"

 [форматирующая строка

Процедура начинается с создания нового фрейма в конце старого. Для этого

значение регистра ESP копируется в указатель фрейма ЕВР. Затем п сравнивается
с 1, и если п>1, то совершается переход к оператору el se. Тогда программа then поме-
щает в стек три значения: адрес форматирующей строки, i и j, и вызывает саму себя.

Параметры помещаются в стек в обратном порядке, поскольку это требуется

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

После вызова процедуры к регистру ESP прибавляется 12, чтобы удалить пара-

метры из стека. На самом деле они не удаляются из памяти, но корректировка (изме-
нение) регистра ESP делает их недоступными через обычные операции со стеком.

Выполнение части else начинается с L1. Здесь сначала вычисляется выраже-

ние 6-i-j, и полученное значение сохраняется в переменной к. Сохранение значе-
ния в переменной к избавляет от необходимости вычислять это во второй раз.

Затем процедура вызывает сама себя три раза, каждый раз с новыми парамет-

рами. После каждого вызова стек освобождается.

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

деле они совсем несложные. Просто параметры помещаются в стек, и вызывается

процедура.

Решение задачи «Ханойская башня»

на ассемблере UltraSPARC II

А теперь рассмотрим то же самое для UltraSPARC П. Программа приведена в ли-
стинге 5.8. Поскольку программа для UltraSPARC II совершенно нечитаема даже
после длительных тренировок, мы решили определить несколько символов, чтобы

4 2 0

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

прояснить дело. Чтобы такая программа работала, ее перед ассемблированием нуж-
но пропустить через программу под названием срр (препроцессор С). Здесь мы
используем строчные буквы, поскольку ассемблер Pentium II требует этого (это
на тот случай, если читатели захотят напечатать и запустить эту программу).

Листинг 5.8.

 Решение задачи «Ханойская башня» для UltraSPARC II

#define N

 £iO

#define  M i l
#define J £i2
#define

 К «10

#define ParamO SoO

#define Paraml Xol

Idefine Param2 Яо2

#define Scratch XII

.proc 04
.global towers

towers: save *sp.-112. *sp

cmp N, 1
bne Else

sethi

 £hi(format). ParamO

or ParamO. Xlo(format). ParamO
mov I. Paraml
call printf
mov J. Param2
b Done

пор

Else:

Done:

mov 6. К
sub K.J.K

sub K.I,К

/* N - это входной параметр 0 */

/* I - это входной параметр 1 */
/* J - это входной параметр 2 */

/* К - это локальная переменная 0 */

/* ParamO - это выходной параметр 0 */
/* Paraml - это выходной параметр 1 */
/* Param2 - это выходной параметр 2 */
/*примеч.: срр использует запись комментариев как в языке С*/

if(n= 1)

if (n != 1) goto Else

printf("Переместить диск с

 %d

 на

 %d\n".

 i,

ParamO = адрес форматирующей строки

Paraml = i
вызов printf ДО установки параметра 2 (j)
пустая операция для установки параметра 2
завершение
вставляет пустую операцию

начало вычисления к = б -i-j
k-6-j

j)

add N, -1. Scratch

mov Scratch, ParamO
mov I. Paraml
call towers
mov K, Param2

mov 1, ParamO
mov I. Paraml
call towers
mov J. Param2

mov Scratch. ParamO

mov K. Paraml
call towers

mov J. Param2

ret

restore

начало процедуры towers(n-l. i. k)

Scratch = n-1

параметр 1 - i

вызов процедуры towers ДО установки параметра 2 (k)

пустая операция после вызова процедуры для установки

параметра2

! начало процедуры towersd. i. j)

! параметр1=1
! вызов процедуры towers ДО установки параметра 2 (j)

! параметр 2 = j

! начало процедуры towers(n-l. k. j)

! параметр 1 « к
! вызов процедуры towers ДО установки параметра 2 (j)

! параметр 2 = j
! выход из процедуры
! вставка пустой команды после ret для восстановления окон

format: .asciz "Переместить диск с

 %d

 на

 %й\п"

По алгоритму версия UltraSPARC идентична версии Pentium II. В обоих слу-

чаях сначала проверяется п, и если п>1, то совершается переход к el se. Основные

Ханойская башня 421

сложности версии UltraSPARC II связаны с некоторыми свойствами архитекту-
ры команд.

Сначала UlraSPARC II должен передать адрес форматирующей строки в printf,

но машина не может просто переместить адрес в регистр, который содержит выхо-
дящий параметр, поскольку нельзя поместить 32-битную константу в регистр за
одну команду. Для этого требуется выполнить две команды: SETHI и OR.

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

корректируется командой RESTORE в конце процедуры. Возможность помещать вы-
ходящие параметры в регистры и не обращаться к памяти дает огромный выиг-
рыш в производительности.

А теперь рассмотрим команду NOP, которая следует за Done. Это пустая опера-

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

Эта особенность распространяется и на вызовы процедур. Рассмотрим первый

вызов процедуры towers в части else. Процедура помещает п-1 в %оО, a i — в %ol,
но совершает вызов процедуры towers до того, как поместит последний параметр
в нужное место. На компьютере Pentium II вы сначала передаете параметры, а затем
вызываете процедуру. А здесь вы сначала передаете часть параметров, затем вызы-
ваете процедуру, и только после этого передаете последний параметр. К тому мо-
менту, когда машина осознает, что она имеет дело с командой CALL, следующую
команду все равно приходится выполнять (из-за конвейеризации системы). А по-
чему бы в этом случае не использовать пустую операцию, чтобы передать послед-
ний параметр? Даже если самая первая команда вызванной процедуры использует
этот параметр, он уже будет на своем месте.

Наконец, рассмотрим часть команды Done. Здесь после команды RET тоже

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

Решение задачи «Ханойская башня»

на ассемблере для JVM

Соответствующая программа дана в листинге 5.9. Решение довольно простое, за

исключением процесса ввода-вывода. Эта программа была порождена компиля-
тором Java, переделана в символический язык ассемблера и обработана опреде-
ленным образом для удобочитаемости. Компилятор JVM хранит три параметра п,
i и j в локальных переменных 0, 1 и 2 соответственно. Локальная переменная к
хранится в локальной переменной 3. Ко всем четырем локальным переменным мож-
но обратиться с помощью 1-байтного кода операции, например

 ILOAD0.

 В резуль-

тате двоичная версия этой программы в JVM получается очень короткой (всего
67 байтов).

4 2 2

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

Листинг 5.9.

 Решение задачи «Ханойская башня» для JVM

IL0ADJ) // лок. переменная 0 = п; помещает в стек п
ICONST_1 // помещает в стек 1
IFJCMPNE  L I //if(n!-l)gotoLl

GETSTATIC #13 // п — 1: эта команда обрабатывает выражение pnntln

NEW #7 // размещает буфер для строки, которую нужно создать
DUP // дублирует указатель на буфер
LDC #2 // помещает в стек указатель на цепочку "перенести диск с"

INVOKESPECIAL #10 // копирует эту цепочку в буфер
ILOAD_1 // помещает в стек i

INVOKEVIRTUAL #11 // превращает i в цепочку и присоединяет к новому буферу

LDC #1 // помещает в стек указатель на цепочку "на"
INVOKEVIRTUAL #12 // присоединяет эту цепочку к буферу

ILOAD_2 // помещает в стек j

INVOKEVIRTUAL #11 // превращает j в цепочку и присоединяет ее к буферу

INVOKEVIRTUAL #15 // преобразование строки
INVOKEVIRTUAL #14 // вызов println

RETURN // выход из процедуры towers

LI: BIPUSH6 // Часть Else: вычисление k = 6-i-j

ILOAD_1 // лок. переменная 1 = i; помещает в стек i

ISUB // вершина стека = 6-i
IL0AD_2 // лок. переменная 2= j; помещает в стек j
ISUB // вершина стека = 6-i-j

ISTORE_3 // лок. перем. 3 - k = 6-i-j: стек сейчас пуст

IL0ADJ) // начало работы процедуры towers(n-l.i. k);помещает в стек п

ICONST_1 // помещает в стек 1
ISUB // вершина стека = п-1
ILOAD_1 // помещает в стек i

IL0AD_3 // помещает в стек к

INVOKESTATIC #16 // вызывает процедуру towers(п-1. i. к)
ICONST_1 // начинается работа процедуры towersQ,
ILOAD_1 // помещает в стек i
IL0AD_2 // помещает в стек j
INVOKESTATIC #16 // вызов процедуры towersd. i. j)
ILOAD_0 " // начало работы процедуры towers(n-l.
ICONSTJ. // помещает в стек 1
ISUB // вершина стека = п-1
IL0AD_3 // помещает в стек к
IL0AD_2 // помещает в стек j
INVOKESTATIC #16 // вызов процедуры towers(n-l, k. j)

RETURN // выход из процедуры towers

Сначала программа помещает в стек параметр п и константу 1, а затем сравнива-

ет их с помощью команды

 IFICMPNE.

 Эта команда обратна команде IF_ICMPEQ, которая

используется в машине IJVM. Она выталкивает из стека два операнда и совершает
переход, если они различны.

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

Следующие 13 команд определяют буфер строки и строят в нем цепочку, которая
затем передается в println для вывода на экран. После завершения печати совер-
шается выход из процедуры.

Если говорить кратко, эти 13 команд размещают буфер строки в «кучу» и

заполняют его. Команда GETSTATIC индексирует набор констант, чтобы получить
слово 13, которое содержит указатель на дескриптор для буфера строки. Команда

NEW

 использует этот дескриптор для размещения буфера строки в «куче». Следую-

j) помещает в стек 1

k.  j ) ; помещает в стек п