Boroda_2

Во время первого прохождения цикла регистр R2 принимает значение 0 (так регистр инициализируется), поэтому нужное нам слово А₀ находится в ячейке с адресом 124 300. Это слово загружается в регистр R4. При следующем прохож­дении цикла R2 принимает значение 4, поэтому нужное нам слово А_{ находится в ячейке с адресом 124 304 и т. д.

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

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

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

LOOP: MOV R4,(R2+R5)

AND R4,(R2+R6)

Было бы идеально, если бы существовал режим адресации по сумме двух ре­гистров без смещения. В то же время даже команда с 8-разрядным смещением была бы большим достижением, поскольку оба смещения можно сделать нуле­выми. Однако если смещение всегда составляет 32 бита, тогда мы ничего не вы­играем, использовав такой режим адресации. На практике машины с относительной индексной адресацией обычно имеют форму с 8- или 16-разрядным смещением.

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

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

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

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

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

Существует несколько алгоритмов для превращения инфиксных формул в обратную польскую запись. Мы рассмотрим переработанный алгоритм, идея которого предложена Э. Дейкстра (Е. W. Dijkstra). Предположим, что формула состоит из переменных, двухоперандных операторов +, *, /, а также левой и

правой скобок. Чтобы отметить конец формулы, мы будем вставлять символ по­сле ее последнего символа и перед первым символом следующей формулы.

На рис. 5.15 схематично показана железная дорога из Нью-Йорка в Калифор­нию с ответвлением, ведущим в Техас. Каждый символ формулы представлен одним вагоном. Поезд движется на запад (налево). Перед стрелкой каждый ва­гон должен останавливаться и узнавать, должен ли он двигаться прямо в Кали­форнию, или ему нужно по пути заехать в Техас. Вагоны, содержащие перемен­ные, всегда направляются в Калифорнию и никогда не едут в Техас. Вагоны, содержащие все прочие символы, должны перед прохождением стрелки узнавать о содержимом ближайшего вагона, отправившегося в Техас.

В таблице на рис. 5.16 показана зависимость ситуации от того, какой вагон отправился в Техас последним и какой вагон находится у стрелки. Первый вагон (помеченный символом _L) всегда отправляется в Техас.

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

Числа соответствуют следующим ситуациям:

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

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

3. Вагон, находящийся на стрелке, и последний вагон, отправившийся в Техас, угоняются и исчезают (то есть, оба удаляются).

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

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

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

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

Таблица 5.5. Некоторые примеры инфиксных выражений и их эквиваленты в обратной польской

Инфиксная запись	Обратная польская запись
А + В х С	А В С х +
А х В + С	А В х С +
Ах В + С D	А В х С D х +
(А + В)/(С - D)	А В + С D - /
Ах В/С	А В х С /
((А + В) х С + D)/(E + F + G)	AB+CXD+EF+G+/

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

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

Таблица 5.6 иллюстрирует вычисление машиной IJVM следующего выраже­ния:

(8 + 2 х 5) / (1 + 3 х 2 - 4).

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

825х+132х + 4-/.

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

Таблица 5.6. Использование стека для вычисления формулы в обратной польской записи

Шаг	Оставшаяся цепочка	Команда	Стек
1	8 2 5 х + 1 3 2 х + 4 - /	BIPUSH 8	8
2	2 5 х + 1 3 2 х + 4 - /	BIPUSH 2	8, 2
3	5х+132х+4-/	BIPUSH 5	8, 2, 5
4	х+132х+4-/	IMUL	8, 10
5	+132Х+4-/	IADD	18
6	1 3 2 х + 4 - /	BIPUSH 1	18, 1
7	3 2 х + 4 - /	BIPUSH 3	18, 1, 3
8	2 х + 4 - /	BIPUSH 2	18, 1,3, 2
9	х + 4 - /	IMUL	18, 1, 6
10	+ 4-/	IADD	18, 7
11	4-/	BIPUSH 4	18, 7, 4
12	-/	ISUB	18, 3
13	/	IDIV	6

Режимы адресации в командах перехода

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

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

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

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

Ортогональность кодов операций и режимов адресации

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

Рассмотрим форматы 32-разрядных команд для трехадресной машины (рис. 5.17). Здесь поддерживаются до 256 кодов операций. В варианте 1 формата каждая команда имеет два входных регистра (источника) и один выходной ре­гистр (приемник). Этот формат используется для всех арифметических и логи­ческих команд.

Неиспользованное 8-разрядное поле в конце команды может потребоваться для дальнейшей дифференциации команд. Например, можно иметь один код для всех операций с плавающей точкой, а различаться эти операции будут по допол­нительному полю. Кроме того, если установлен бит 23, тогда задействуется ва­риант 2 формата, а второй операнд уже является не регистром, а 13-разрядной непосредственной константой со знаком. Команды LOAD и STORE тоже могут ис­пользовать этот формат для обращения к памяти при индексном способе адреса­ции.

Необходимо также иметь небольшое число дополнительных команд (напри­мер, команд условных переходов), но они легко подходят под вариант 3 формата. Например, можно приписать один код операции каждому (условному) переходу, вызову процедуры и т. д., тогда останется 24 бита для смещения по счетчику ко­манд. Если предположить, что это смещение считается в словах, диапазон будет составлять 32 Мбайт. Несколько кодов операций можно зарезервировать для команд LOAD и STORE, которым нужны длинные смещения в варианте 3 формата.

Теперь рассмотрим структуру двухадресной машины, в которой в качестве любого операнда может использоваться слово из памяти (рис. 5.18). Такая машина умеет складывать слово памяти с регистром, регистр со словом памяти, два регистра и два слова памяти. В настоящее время обращение к памяти свя­зано со значительными издержками, поэтому такая структура не очень распро­странена, но если с развитием технологий обращаться к памяти станет менее на­кладно, получится простое и эффективное решение. Машины PDP-11 и VAX, в которых использовались похожие форматы, были очень популярны и домини­ровали на рынке мини-компьютеров в течение двух десятилетий.

Биты 8 3 5 4 3 5 4

После каждого действия производится новое сравнение вагона, находящегося у стрелки (это может быть тот же вагон, что и в предыдущем сравнении, а может Здесь мы снова имеем 8-разрядный код операции, но теперь у нас есть по 12 бит для задания источника и приемника. Для каждого операнда 3 бита позво­ляют указать режим адресации, 5 бит — регистр и 4 бита — смещение. Имея 3 би­та для задания режима адресации, мы можем поддерживать непосредственную, прямую, регистровую, косвенную регистровую индексную и стековую адреса­ции, и при этом еще остается место для двух дополнительных режимов, которые, возможно, появятся в будущем. Это простая система, которую легко компилиро­вать, в то же время она достаточно гибкая, особенно если счетчик команд, указа­тель стека и указатель локальных переменных находятся среди регистров обще­го назначения, к которым можно получить доступ.

Единственная проблема в том, что при прямой адресации нам нужно большее количество битов для адреса. В машинах PDP-11 и VAX к команде было добав­лено дополнительное слово для указания адреса каждого прямо адресуемого операнда. Мы тоже могли бы использовать один из двух доступных режимов ад­ресации для индексной адресации с 32-разрядным смещением, которое следует за командой. Тогда в худшем случае при сложении двух слов памяти, когда обра­щение к обоим операндам производится в режиме прямой адресации или с ис­пользованием длинной индексной формы, команда была бы размером 96 бит и занимала бы 3 цикла шины (один для команды и два для данных). В то же время для прибавления произвольного слова памяти к другому произвольному слову памяти большинству RISC-систем потребовалось бы по крайней мере 96 бит, а может и больше, на что нужно по крайней мере 4 цикла шины.

Форматы, изображенные на рис. 5.18, допускают самые разные варианты. В данной системе с помощью одной 32-разрядной команды, при условии что пе­ременные i и j находятся среди первых 16 локальных переменных, можно вы­полнить следующую операцию: i = j;

Для переменных, расположенных после первых 16, нам потребуется перейти к 32-разрядным смещениям. Можно также придумать формат с одним 8-разряд- ным смещением вместо двух 4-разрядных при условии, что это смещение может

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

Режимы адресации процессора Pentium 4

Режимы адресации процессора Pentium 4 чрезвычайно нерегулярны и зависят от формата конкретной команды — 16- или 32-разрядная. Мы не будем рассматри­вать 16-разрядные команды, вполне достаточно 32-разрядных. Поддерживаемые режимы адресации включают непосредственную, прямую, регистровую, косвен­ную регистровую, индексную и специальную адресацию для обращения к эле­ментам массива. Проблема заключается в том, что не все режимы применимы ко всем командам и не все регистры могут использоваться во всех режимах адреса­ции. Это значительно усложняет задачу разработчика компилятора.

Как показано на рис. 5.10, для управления режимами адресации имеется со­ответствующий байт. Один из операндов определяется по комбинации полей MOD и R/М. Второй операнд всегда является регистром и определяется по зна­чению поля REG. В табл. 5.7 приведен список 32 комбинаций значений 2-раз- рядного поля MOD и 3-разрядного поля R/М. Например, если оба поля равны 0, операнд считывается из ячейки памяти с адресом, который содержится в регист­ре ЕАХ.

Таблица 5.7. 32-разрядные режимы адресации процессора Pentium 4 (М[х] — это слово в памяти с адресом х)

R/M		MOD
	00	01	10	11
ООО	М[ЕАХ]	М[ЕАХ + смещение 8]	М[ЕАХ + смещение 32]	ЕАХ или AL
001	М[ЕСХ]	М[ЕСХ + смещение 8]	М[ЕСХ + смещение 32]	ЕСХ или CL
010	M[EDX]	M[EDX + смещение 8]	M[EDX + смещение 32]	EDX или DL
011	М[ЕВХ]	М[ЕВХ + смещение 8]	М[ЕВХ + смещение 32]	ЕВХ или BL
100	SIB	SIB со смещением 8	SIB со смещением 32	ESP или АН
101	Прямая адресация	М[ЕВР + смещение 8]	М[ЕВР + смещение 32]	EBP или СН
110	M[ESI]	M[ESI + смещение 8]	M[ESI + смещение 32]	ESI или DH
111	М [EDI]	M[EDI + смещение 8]	M[EDI + смещение 32]	EDI или ВН

Колонки 01 и 10 включают режимы адресации, при которых значение регист­ра прибавляется к 8- или 32-разрядному смещению, следующему за командой. Если выбрано 8-разрядное смещение, оно перед сложением получает 32-разряд­ное знаковое расширение. Например, команда ADD с полем R/M = 011, полем MOD = 01 и смещением, равным шести, вычисляет сумму регистра ЕВХ и 6, и в качестве одного из операндов считывает слово из полученного адреса памя­ти. Значение регистра ЕВХ не изменяется.

При MOD =11 предоставляется возможность выбора из двух регистров. Для команд со словами берется первый вариант, для команд с байтами — второй.

Отметим, что здесь не все регулярно. Например, нельзя выполнить косвенную адресацию через EBP или прибавить смещение к ESP.

Иногда вслед за байтом MODE следует дополнительный байт SIB (см. рис. 5.10). Байт SIB определяет масштабный коэффициент и два регистра. Когда присутствует байт SIB, адрес операнда вычисляется путем умножения индексно­го регистра на 1, 2, 4 или 8 (в зависимости от значения поля SCALE), прибав­лением его к базовому регистру и, наконец, возможным прибавлением 8- или 32-разрядного смещения, в зависимости от значения поля MOD. Практически все регистры могут использоваться и в качестве индекса, и в качестве базы.

Режимы, получаемые посредством байта SIB, могут пригодиться для обраще­ния к элементам массива. Рассмотрим следующую Java-команду:

for (1=0; i<n; i++) a[i]=0;

Здесь a — массив 4-байтных целых чисел, относящийся к текущей процедуре. Обычно регистр EBP используется для указания на базу стекового фрейма, ко­торый содержит локальные переменные и массивы, как показано на рис. 5.19. Компилятор должен хранить значение i в регистре ЕАХ. Для доступа к элементу a[i] он будет использовать режим с байтом SIB, в котором адрес операнда равен сумме значений 4 ЕАХ, EBP и 8. Эта операция может сохраняться в a[i] за одну команду.

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

Мы представили несколько возможных компромиссов, с которыми постоянно сталкиваются разработчики. Обычно перед тем, как воплотить какую-либо идею в кремнии, выполняются многочисленные моделирующие прогоны, но для этого нужно иметь представление о том, как будет использоваться машина. Можно гарантировать, что разработчики машины 8088 тестировали ее без веб-браузера. Решения, принятые 20 лет назад, могут оказаться абсолютно неудачными с точ­ки зрения современных приложений. В то же время, включив в машину ка­кую-нибудь функцию, из-за требования обратной совместимости избавиться от нее будет уже невозможно.

Режимы адресации процессора UltraSPARC III

В архитектуре команд процессора UltraSPARC все команды поддерживают ре­жим непосредственной или регистровой адресации, за исключением тех команд, которые обращаются к памяти. При регистровой адресации 5 бит просто сообщают, какой регистр нужно использовать. При непосредственной адресации в качестве данных используется 13-разрядная константа со знаком. Для арифметических, логических и других подобного рода команд никаких других режимов адресации не используется.

К памяти обращаются команды трех типов: загрузки (LOAD), сохранения (STORE) и синхронизации мультипроцессора. Для команд LOAD и STORE поддерживаются два режима обращения к памяти. В первом режиме вычисляется сумма двух ре­гистров, а затем полученное значение используется для косвенной адресации. Второй режим представляет собой обычное индексирование с 13-разрядным смещением со знаком.

Режимы адресации процессора 8051

Схема адресации процессора 8051 достаточно стандартна. Предусмотрено пять основных режимов адресации. Простейший из них, называемый неявной адреса­цией, применяется в сумматоре. Многие команды комбинируют операнды со значением, накопленным в сумматоре; так работают команды сложения и вычи­тания операндов, логические операции И и ИЛИ с операндами. Команды, обра­щающиеся к сумматору, не имеют битов, указывающих на это. Факт применения сумматора неявно подразумевается в коде операции.

Второй режим адресации — регистровая адресация, при которой операнд по­мещается в регистр. Регистры при этом могут быть как входными (источниками значений), так и выходными (приемниками значений). Третий режим — прямая адресация, когда операнд находится в ячейке памяти, адрес которой указан в ко­манде. Четвертый режим — косвенная регистровая адресация, подразумевающая размещение в регистре указателя на операнд. Поскольку разрядность обычных регистров составляет 8 бит, операнды с такой адресацией должны занимать ниж­ние 256 байт памяти. В последнем, пятом, режиме, который называется непо­средственной адресацией, предполагается, что операнд является частью команды.

Помимо вышеупомянутых, в 8051 предусмотрен специализированный режим адресации, применяемый некоторыми командами для доступа к памяти. Как вы помните, к микросхеме 8051 можно подключить до 64 Кбайт внешней памяти для программ и столько же внешней памяти для данных. К этим модулям тоже нужно как-то обращаться. За взаимодействие с внешней памятью программ отвечают две команды: команда LJMP за счет 16-разрядного смещения может переходить к любому адресу в памяти, а команда LCALL аналогичным способом может вызывать любые размещенные в памяти подпрограммы.