В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 22
Текст из файла (страница 22)
Оперативная память программы обычно состоит из нескольких основных разделов: стек (магазин), куча, область статических данных (инициализированных и неинициализированных). Наиболее сложной является работа со стеком. Вообще говоря, стек периода исполнения необходим для программ не на всех языках программирования. Например, в ранних версиях Фортрана нет рекурсии, так чтопрограмма может исполняться без стека.
С другой стороны, исполнениепрограммы с рекурсией может быть реализовано и без стека (того же эффекта можно достичь, например, и с помощью списковых структур). Однако, для эффективной реализации пользуются стеком, который, какправило, поддерживается на уровне машинных команд.Рассмотрим схему организации магазина периода выполнения дляпростейшего случая (как, например, в языке Паскаль), когда все переменные в магазине (фактические параметры и локальные переменные)9.2. ДИНАМИЧЕСКАЯ ОРГАНИЗАЦИЯ ПАМЯТИ139имеют известные при трансляции смещения. Магазин служит для хранения локальных переменных (и параметров) и обращения к ним в языках, допускающих рекурсивные вызовы процедур. Еще одной задачей,которую необходимо решать при трансляции языков с блочной структурой – обеспечение реализации механизмов статической вложенности.Пусть имеется следующий фрагмент программы на Паскале:procedure P1;var V1;procedure P2;var V2;begin...P2;V1:=...V2:=......end;begin...P2;...end;В процессе выполнения этой программы, находясь в процедуре P2,мы должны иметь доступ к последнему экземпляру значений переменных процедуры P2 и к экземпляру значений переменных процедуры P1,из которой была вызвана P2.
Кроме того, необходимо обеспечить восстановление состояния программы при завершении выполнения процедуры.Мы рассмотрим две возможные схемы динамической организациипамяти: схему со статической цепочкой и с дисплеем в памяти. В первом случае все статические контексты связаны в список, который называется статической цепочкой; в каждой записи для процедуры в магазине хранится указатель на запись статически охватывающей процедуры (помимо, конечно, указателя динамической цепочки – указателяна “базу” динамически предыдущей процедуры).
Во втором случае дляхранения ссылок на статические контексты используется массив, называемый дисплеем. Использование той или иной схемы определяется,помимо прочих условий, прежде всего числом адресных регистров.9.2.1Организация магазина со статической цепочкойИтак, в случае статической цепочки магазин организован, как это изображено на рис. 9.1.Таким образом, на запись текущей процедуры в магазине указываетрегистр BP (Base Pointer), с которого начинается динамическая цепочка.ГЛАВА 9. ГЕНЕРАЦИЯ КОДА140FbgbfZevgucZ^j_kKhojZg_ggu_j_]bklju\dexqZy/3L_dmsbcklZlbq_kdbcmjh\_gvEhdZevgu_iZjZf_ljuIj_^u^msbc%3%3LhqdZ\ha\jZlZH[eZklvihke_^g_c\ua\Zgghcijhp_^mjuNZdlbq_kdb_iZjZf_ljuKhojZg_ggu_j_]bkljuIj_^u^msbcklZlbq_kdbcmjh\_gvIj_^u^msbc/3EhdZevgu_iZjZf_lju/3'HOWDIj_^u^msbc%3x x x x xFZdkbfZevgucZ^j_kРис. 9.1:На статическую цепочку указывает регистр LP (Link Pointer). В качестверегистров BP и LP в различных системах команд могут использоватьсяуниверсальные, адресные или специальные регистры.
Локальные переменные отсчитываются от регистра BP вверх, фактические параметры –вниз с учетом памяти, занятой точкой возврата и самим сохраненнымрегистром BP.Вызов подпрограмм различного статического уровня производитсянесколько по-разному. При вызове подпрограммы того же статическогоуровня, что и вызывающая подпрограмма (например, рекурсивный вызов той же самой подпрограммы), выполняются следующие команды:Занесение фактических параметров в магазинJSR AКоманда JSR A продвигает указатель SP, заносит PC на верхушку магазина и осуществляет переход по адресу A.
После выполнения этих команд состояние магазина становится таким, как это изображено на рис. 9.2.9.2. ДИНАМИЧЕСКАЯ ОРГАНИЗАЦИЯ ПАМЯТИ141Занесение BP, отведение локальных, сохранение регистров делает вызываемая подпрограмма (см. ниже).L_dmsbcklZlbq_kdbcmjh\_gvLhqdZ\ha\jZlZ63NZdlbq_kdb_iZjZf_ljuKhojZg_ggu_j_]bklju\dexqZy/3EhdZevgu_iZjZf_ljuIj_^u^msbc%3%3LhqdZ\ha\jZlZNZdlbq_kdb_iZjZf_ljuKhojZg_ggu_j_]bkljuIj_^u^msbcklZlbq_kdbcmjh\_gvIj_^u^msbc/3/3EhdZevgu_iZjZf_ljuIj_^u^msbc%3x x x x xРис. 9.2:При вызове локальной подпрограммы необходимо установить указатель статического уровня на текущую подпрограмму, а при выходе –восстановить его на старое значение (охватывающей текущую).
Для этого исполняются следующие команды:Занесение фактических параметров в магазинMOVE BP, LPSUB Delta, LPJSR AЗдесь Delta – размер локальных вызывающей подпрограммы плюсдвойная длина слова. Магазин после этого принимает состояние, изображенное на рис. 9.3.
Предполагается, что регистр LP уже сохраненГЛАВА 9. ГЕНЕРАЦИЯ КОДА142среди сохраняемых регистров, причем самым первым (сразу после локальных переменных).После выхода из подпрограммы в вызывающей подпрограмме выполняется командаMOVE (LP), LPкоторая восстанавливает старое значение статической цепочки. Если выход осуществлялся из подпрограммы 1-го уровня, эту команду выполнять не надо, поскольку для 1-го уровня нет статической цепочки.L_dmsbcklZlbq_kdbcmjh\_gvLhqdZ\ha\jZlZNZdlbq_kdb_iZjZf_ljuKhojZg_ggu_j_]bkljuIj_^u^msbcklZlbq_kdbcmjh\_gv63Ij_^u^msbc/3EhdZevgu_iZjZf_ljuIj_^u^msbc%3/3'HOWD%3x x x x xРис. 9.3:При вызове подпрограммы меньшего, чем вызывающая, уровня выполняются следующие команды:Занесение фактических параметров в магазинMOVE (LP), LP /* столько раз, какова разностьуровней вызывающей и вызываемой ПП */JSR AТем самым устанавливается статический уровень вызываемой подпрограммы.
После выхода из подпрограммы выполняется командаMOVE -Delta(BP), LP9.2. ДИНАМИЧЕСКАЯ ОРГАНИЗАЦИЯ ПАМЯТИ143восстанавливающая статический уровень вызывающей подпрограммы.Тело подпрограммы начинается со следующих команд:LINK BP , -размер_локальныхMOVEM -(SP)Команда LINK BP, размер_локальных эквивалентна трем командам:MOVE BP, -(SP)MOVE SP, BPADD -размер_локальных, SPКоманда MOVEM сохраняет в магазине регистры.В результате выполнения этих команд магазин приобретает вид, изображенный на рис. 9.1.Выход из подпрограммы осуществляется следующей последовательностью команд:MOVEM (SP)+UNLK BPRTD размер_фактическихКоманда MOVEM восстанавливает регистры из магазина. Команда UNLK BPэквивалентна такой последовательности команд:MOVE BP,SPMOVE (SP),BPADD #4, SP /* 4 - размер слова */Команда RTD размер_фактических, в свою очередь, эквивалентна последовательностиADD размер_фактических+4, SPJMP -размер_фактических-4(SP)После ее выполнения магазин восстанавливается до состояния, котороебыло до вызова.В зависимости от наличия локальных переменных, фактических параметров и необходимости сохранения регистров каждая из этих командможет отсутствовать.9.2.2Организация магазина с дисплеемРассмотрим теперь организацию магазина с дисплеем.
Дисплей – этомассив (DISPLAY) , i-й элемент которого представляет собой указатель наобласть активации последней вызванной подпрограммы i-го статического уровня. Доступ к переменным самой внутренней подпрограммы осуществляется через регистр BP. Дисплей может быть реализован либо через регистры (если их достаточно), либо через массив в памяти.ГЛАВА 9. ГЕНЕРАЦИЯ КОДА144При вызове процедуры следующего (по отношению к вызывающей)уровня в дисплее отводится очередной элемент. Если вызывающая процедура имеет статический уровень i, то при вызове процедуры уровняj 6 i элементы дисплея j, ... , i должны быть скопированы (обычно в стеквызывающей процедуры), текущим уровнем становится j и в DISPLAY[j]заносится указатель на область активации вызываемой процедуры. Поокончании работы вызываемой процедуры содержимое дисплея восстанавливается из стека.Иногда используется комбинированная схема – дисплей в магазине.Дисплей хранится в области активации каждой процедуры.
Формирование дисплея для процедуры осуществляется в соответствии с правилами, описанными выше.Отдельного рассмотрения требует вопрос о технике передачи фактических параметров. Конечно, в случае простых параметров (например,чисел) проблем не возникает. Однако передача массивов по значению –операция довольно дорогая, поэтому с точки зрения экономии памятицелесообразнее сначала в подпрограмму передать адрес массива, а затемуже из подпрограммы по адресу передать в магазин сам массив.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
