Практическая работа № 39
«Стек»

Из учебника (§ 61) вы уже знаете, что при вызове процедур важнейшую роль играет стек – область оперативной памяти, в которой хранятся адрес возврата из процедуры и локальные переменные. В этой практической работе мы познакомимся с работой стека на примере учебного компьютера «ЛамПанель», с которым вы уже встречались при изучении глав 4 и 5.

Возможности программы «ЛамПанель»

Программа «ЛамПанель» – это модель процессора, который управляет ламповой панелью, то есть, может с помощью специальных команд зажигать и гасить определенные лампочки.

Стек в программе «ЛамПанель» размещается в оперативной памяти, вместе с программой и данными. Оперативная память имеет размер 256 байт, адреса ячеек (байтов) изменяются от 0 до 255 = FF₁₆. Программа начинается с адреса 0 (в начале области памяти), данные обычно расположены сразу за ней. Стек находится в самом конце оперативной памяти и «растет вверх». Это значит, что первое записанное в стек 16-битное слово имеет адрес FE₁₆ (последние два байта памяти), следующее записанное слово – адрес FC₁₆ и т.д. Как же компьютер разбирается, где начинается стек и сколько чисел туда записано?

В процессоре есть специальный регистр SP (от англ. Stack Pointer – указатель стека), в котором хранится адрес вершины стека, то есть последнего записанного в стек 16-битного значения. При запуске программы в регистр SP записывается значение 100₁₆ (область 1 на рисунке). Этот адрес находится за границами оперативной памяти и говорит о том, что стек пуст.

Для того, чтобы записать значение из регистра общего назначения в стек, используется команда PUSH (от англ. push – втолкнуть). Например, при выполнении этих команд в стек будет записано значение регистра R0:

MOV 1234,R0

PUSH R0

Обратите внимание на значение регистра SP – оно стало равно FE₁₆ и теперь указывает на последнее слово памяти (область 2 на рисунке), в котором записано число 1234₁₆ – значение регистра R0 (сначала младший байт, потом старший).

Добавим к программе еще одну команду, которая «снимает» 16-битное значение с вершины стека и записывает его в регистр R2:

POP R2

После этого наблюдаем следующее (см. рисунок ниже):
• в регистре R2 находится то же значение 1234₁₆, которое было в R0 (область 1)
• регистр SP содержит значение 100₁₆, которое говорит о том, что стек пуст (область 2)
• в последних двух байтах памяти осталось значение 1234₁₆, которое было записано в стек (область 3), но теперь оно уже не является часть стека, поскольку регистр SP изменен.

Вызов подпрограмм

Как вы знаете, подпрограммы – это вспомогательные алгоритмы. Напишем подпрограмму, которая возводит в квадрат значение регистра R0. Эта подпрограмма содержит всего одну команду умножения (умножить R0 на R0, записать результат в R0):

MUL R0, R0

В начале подпрограммы нужно поставить метку (имя подпрограммы), а в конце – команду возврата RET (от англ. return – возврат), по которой процессор возвращается в точку вызова. Таким образом, вся подпрограмма, которую мы назовём SQR, выглядит так:

SQR:

     MUL R0, R0

RET

«Паспорт» этой подпрограммы такой:

Вход: число в регистре R0

Выход (результат): квадрат числа в регистре R0

Подпрограмма располагается ниже основной программы. Чтобы вызвать подпрограмму, используют команду CALL (от англ. call – вызвать), после которой записывают имя подпрограммы – метку, с которой она начинается, адрес точки входа. Вот вся программа вместе с подпрограммой:

MOV 12,R0 ; записать начальное значение в R0
CALL SQR ; вызвать подпрограмму SQR
STOP ; конец основной программы
SQR: ; точка входа подпрограммы
MUL R0, R0 ; тело подпрограммы – возведение R0 в квадрат
RET ; возврат из подпрограммы

Остается один вопрос: как процессор определяет адрес возврата из подпрограммы, когда выполняется команда RET? Заметим, что в самой команде RET адрес не указан. Дело в том, что адрес перехода заранее определить нельзя (нельзя поставить команду безусловного перехода JMP), потому что подпрограмма может вызываться из разных мест программы, в том числе из других подпрограмм. Эту проблему оказалось просто решить с помощью стека:

• команда CALL записывает в стек адрес возврата из подпрограммы, то есть адрес команды, следующей за командой CALL; поскольку регистр PC (программный счётчик) всегда содержит адрес следующей команды, процессору достаточно просто скопировать содержимое регистра PC в стек;
• после этого в регистр записывается адрес указанной подпрограммы и ей передается управление;
• команда RET снимает с вершины стека адрес возврата и записывает его в регистр PC, таким образом управление передается следующей команде вызывающей программы.

Сохранение регистров

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

MOV R0,R1 ; скопировать R0 в R1
MUL R0,R0 ; возвести R0 в квадрат
MUL R1,R0 ; умножить R1 на R0

Все хорошо, но… мы стерли значение регистра R1, которое было до вызова подпрограммы. Чтобы при вызове подпрограммы регистры не стирались, их нужно сохранять при входе в подпрограмму и восстанавливать перед самым выходом. Где сохранять? Самый простой выход – использовать стек, сохранять командой PUSH, и восстанавливать командой POP. Таким образом полный текст подпрограммы CUBE выглядит так:

CUBE:
PUSH R1 ; сохраняем R1
MOV R0,R1 ; скопировать R0 в R1
MUL R0,R0 ; возвести R0 в квадрат
MUL R1,R0 ; умножить R1 на R0
POP R1 ; восстанавливаем R1
RET

Передача параметров в подпрограмму

В предыдущих примерах вы уже увидели, что параметры (дополнительные данные) могут передаваться в подпрограмму через регистры общего назначения R0-R3. Но этих регистров всего четыре, поэтому таким способом можно передать только четыре 16-битных числа. А что, если нужно передать, например, массив из 100 элементов? В этом случае на помощь приходит стек.

Перед вызовом подпрограммы в стек записываются все передаваемые параметры. рассмотрим сначала «игрушечную» задачу – написать подпрограмму, которая возводит число в квадрат, причем это число передается через стек. Результат должен быть помещен в регистр R0.

Перед вызовом подпрограммы запишем в стек значение R0:

0000 MOV 12,R0 ; это число нужно возвести в квадрат
0004 PUSH R0 ; запишем его в стек
0006 CALL SQR ; вызов подпрограммы
000A STOP
000C SQR:
... ; здесь будет подпрограмма

Если посмотреть на стек (в нижней части оперативной памяти), то после выполнения команды PUSH R0 он выглядит так:

SP -> 00FE 0012

Указатель стека SP содержит адрес 00FE и указывает на последнее 16-битное слово памяти. В стеке находится число 12₁₆ – значение, передаваемое в подпрограмму.

Когда выполнится команда CALL, в стек запишется адрес возврата из подпрограммы, то есть адрес 000A₁₆, по которому расположена команда STOP. На этот адрес и будет указывать регистр SP:

SP-> 00FC 000A

         00FE 0012

Теперь займемся подпрограммой: как «достать» переданное значение? Сначала нужно скопировать содержимое указателя стека в какой-то регистр общего назначения, например, в R0:

MOV SP,R0

Теперь в R0 находится адрес вершины стека, но там лежит адрес возврата. Чтобы получить адрес переданного параметра, нужно увеличить R0 на 2:

ADD 2,R0

Теперь можно взять значение по этому адресу и записать его в тот же регистр R0:

MOV (R0),R0

Запись (R0) означает «значение, находящееся в памяти по адресу, записанному в R0», это так называемый косвенный способ адресации, когда в регистре находится адрес данных, а не значение. Теперь в R0 уже получено переданное число, и можно возвести его в квадрат. Вот полная подпрограмма:

SQR:
MOV SP,R0
ADD 2,R0
MOV (R0),R0
MUL R0,R0
RET

Остается один вопрос – кто же будет освобождать стек, удаляя из него параметры подпрограммы? Тут есть два варианта. Этим может заниматься вызывающая программа – после вызова подпрограмму нужно использовать команду POP. Кроме того, это может делать и процедура – для этого нужно применить команду RET с параметром, который обозначает количество байт, которые нужно «сбросить» со стека. Например, в нашем случае можно применить команду

RET 2

которая освободит 2 байта (удалит один параметр). Отметим, что параметр команды RET – четное число, записанное в шестнадцатеричной системе счисления.

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

Рекурсия

Для процессора рекурсивная подпрограмма ничем не отличается от «обычной». Только внутри рекурсивной подпрограммы есть вызов CALL по адресу той же самой подпрограммы.

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

Факториал числа вычисляется как произведение всех натуральных чисел от 1 до : . Основная идея подпрограммы может быть записана на псевдокоде так:

R1:=R0

R0:=R0-1

вычисляем факториал R0 (вызов процедуры)

R0:=R0*R1

Перевод на язык ассемблера дает:

FACT:
MOV R0,R1
SUB 1,R0
CALL FACT
MUL R1,R0
FINISH:
RET

Однако, выполнение этой подпрограммы никогда не закончится, потому что вызовы никогда не остановятся. Нужно добавить условие выхода: если R0=1, нужно выйти из подпрограммы, то есть перейти на последнюю команду RET (перед ней должна быть метка):

FACT:
CMP 1,R0
JZ FINISH
MOV R0,R1
SUB 1,R0
CALL FACT
MUL R1,R0
FINISH:
RET

Остается еще один недостаток – подпрограмма изменяет значение регистра R1. Нужно при входе в процедуру сохранить его (в стеке), а перед выходом – восстановить. Это вы уже можете сделать самостоятельно.

Задание на практическую работу

1. Запустите тренажёр «ЛамПанель». Напишите и отладьте программу, которая меняет местами значение регистров R2 и R3 с помощью стека (не используя других регистров общего назначения).

Программа:

Опишите, как работает стек при выполнении этой программы:

2. Введите текст программы

MOV 12,R0
CALL SQR
STOP
SQR:
MUL R0,R0
RET

Заполните таблицу, выполнив программу пошагово с помощью клавиши F7 (пошаговое выполнение со входом в подпрограммы):

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

Программа:

4. Напишите и отладьте программу с подпрограммой, которая и строит RGB-код цвета, 4-битные составляющие которого (R, G и B), записаны соответственно в регистры R0, R1 и R2. Результат должен быть получен в регистре R0.

Программа:

5. Выполните предыдущее задание при условии, что параметры передаются через стек, а значения регистров R1 и R2 не должны измениться.

Программа:

6. Отладьте программу с рекурсивной подпрограммой, которая вычисляет факториал числа, записанного в регистр R0. При выполнении в пошаговом режиме (клавиша F7) наблюдайте, как изменяется регистр SP и содержимое стека.

Программа:

7. Решите задачу предыдущего пункта, используя подпрограмму без рекурсии.

Программа: