В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 31
Текст из файла (страница 31)
Динамическая организация памятиДинамическая организация памяти — это организация памяти периода исполнения программы. Оперативная память программы обычно состоитиз нескольких основных разделов: магазин, куча, область статических данных(инициализированных и неинициализированных). Наиболее сложной является работа с магазином. Вообще говоря, магазин периода исполнения необходим для программ не на всех языках программирования. Например, в раннихверсиях Фортрана нет рекурсии, так что программа может исполняться безмагазина. С другой стороны, исполнение программы с рекурсией может бытьреализовано и без магазина (того же эффекта можно достичь, например,и с помощью списковых структур).
Однако, для эффективной реализациипользуются магазином, который, как правило, поддерживается на уровнемашинных команд.Рассмотрим схему организации магазина периода выполнения для простейшего случая (как, например, в языке Паскаль), когда все переменные9.2. Динамическая организация памяти165в магазине (фактические параметры и локальные переменные) имеют смещения, известные при трансляции. Магазин служит для хранения локальныхпеременных (и параметров) и обращения к ним в языках, допускающихрекурсивные вызовы процедур. Еще одной задачей, которую необходимо решать при трансляции языков с блочной структурой, является обеспечениереализации механизмов статической вложенности.
Пусть имеется следующийфрагмент программы на Паскале: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.166Глава 9. Генерация кодаРис. 9.1Таким образом, на запись текущей процедуры в магазине указывает регистр BP (Base Pointer), с которого начинается динамическая цепочка.
На статическую цепочку указывает регистр LP (Link Pointer). В качестве регистровBP и LP в различных системах команд могут использоваться универсальные,адресные или специальные регистры. Локальные переменные отсчитываютсяот регистра BP вверх, фактические параметры — вниз с учетом памяти,занятой точкой возврата и самим сохраненным регистром BP.Вызов подпрограмм различного статического уровня производитсянесколько по-разному. При вызове подпрограммы того же статическогоуровня, что и вызывающая подпрограмма (например, рекурсивный вызов тойже самой подпрограммы), выполняются следующие команды:Занесение фактических параметров в магазинJSR AКоманда JSR A продвигает указатель SP, заносит PC на верхушку магазина и осуществляет переход по адресу A. После выполнения этих командсостояние магазина становится таким, как это изображено на рис.
9.2. Занесение BP, отведение локальных, сохранение регистров делает вызываемаяподпрограмма.При вызове локальной подпрограммы необходимо установить указательстатического уровня на текущую подпрограмму, а при выходе — восстановить9.2. Динамическая организация памяти167Рис. 9.2его на старое значение (подпрограммы, охватывающей текущую). Для этогоисполняются следующие команды:Занесение фактических параметров в магазинMOVE BP, LPSUB Delta, LPJSR AЗдесь Delta — размер локальных переменных вызывающей подпрограммы плюс двойная длина слова. Магазин после этого принимает состояние,изображенное на рис.
9.3. Предполагается, что регистр LP уже сохраненсреди сохраняемых регистров, причем самым первым (сразу после локальныхпеременных).После выхода из подпрограммы в вызывающей подпрограмме выполняетсякомандаMOVE (LP), LPкоторая восстанавливает старое значение статической цепочки.
Если выходосуществлялся из подпрограммы 1-го уровня, эту команду выполнять не надо,поскольку для 1-го уровня нет статической цепочки.При вызове подпрограммы меньшего, чем вызывающая, уровня выполняются следующие команды:168Глава 9. Генерация кодаРис. 9.3Занесение фактических параметров в магазинMOVE (LP), LP /* количество раз равно разностиуровней вызывающей и вызываемой ПП */JSR AТем самым устанавливается статический уровень вызываемой подпрограммы. После выхода из подпрограммы выполняется командаMOVE-Delta(BP), LPвосстанавливающая статический уровень вызывающей подпрограммы.Тело подпрограммы начинается со следующих команд: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),BP9.2. Динамическая организация памятиADD #4, SP169/* 4 - размер слова */Команда RTD размер_фактических, в свою очередь, эквивалентна последовательностиADD размер_фактических+4, SPJMP -размер_фактических-4(SP)После ее выполнения магазин восстанавливается до состояния, которое былодо вызова.В зависимости от наличия локальных переменных, фактических параметров и необходимости сохранения регистров каждая из этих команд можетотсутствовать.9.2.2.
Организация магазина с дисплеем. Рассмотрим теперь организацию магазина с дисплеем. Дисплей — это массив (DISPLAY), i-й элемент которого представляет собой указатель на область активации последнейвызванной подпрограммы i-го статического уровня. Доступ к переменнымсамой внутренней подпрограммы осуществляется через регистр BP. Дисплейможет быть реализован либо через регистры (если их достаточно), либо черезмассив в памяти.Для вызова процедуры следующего (по отношению к вызывающей программе) уровня в дисплее отводится очередной элемент.
Если вызывающаяпроцедура имеет статический уровень i, то при вызове процедуры уровняj 6 i элементы дисплея j , . . . , i должны быть скопированы (обычно в магазинвызывающей процедуры), текущим уровнем становится j и в DISPLAY[j]заносится указатель на область активации вызываемой процедуры. По окончании работы вызываемой процедуры содержимое дисплея восстанавливаетсяиз магазина.Иногда используется комбинированная схема — дисплей в магазине. Дисплей хранится в области активации каждой процедуры.
Формирование дисплея для процедуры осуществляется в соответствии с правилами, описаннымивыше.Отдельного рассмотрения требует вопрос о технике передачи фактических параметров. Конечно, в случае простых параметров (например, чисел)проблем не возникает. Однако передача массивов по значению — операциядовольно дорогая, поэтому с точки зрения экономии памяти целесообразнеесначала в подпрограмму передать адрес массива, а затем уже из подпрограммы по адресу передать в магазин сам массив. В связи с передачей параметровследует упомянуть еще одно обстоятельство.Рассмотренная схема организации магазина допустима только для языковсо статически известными размерами фактических параметров. Однако, например, в языке Модула-2 может быть передан по значению гибкий массив,и в этом случае нельзя статически распределить память для параметров.170Глава 9.
Генерация кодаОбычно в таких случаях заводят так называемый паспорт массива, в которомхранится вся необходимая информация, а сам массив размещается в магазине — в рабочей области регистров, сохраненных выше.9.3. Назначение адресовНазначение адресов переменным, параметрам и полям записей происходитпри обработке соответствующих объявлений. В однопроходном транслятореэто может производиться вместе с построением основной таблицы символов, а соответствующие адреса (или смещения) могут храниться в этой жетаблице. В промежуточном Лидер-представлении объявления сохранены, чтоделает это промежуточное представление машинно-независимым.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
