А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 129
Текст из файла (страница 129)
Стоимость этой команды равна двум, поскольку адрес ячейки памяти М содержится в слове, следующем за командой. ° Команда 10 В1, *100(В2) загружает в регистр В1 значение солГелГз( совпало(100 + солгепж(Р,2))). Стоимость команды равна трем, так как константа 100 хранится в слове, следующем за командой.
В этой главе мы полагаем стоимость программы на целевом языке равной сумме стоимостей отдельных команд, выполняемых при работе программы с заданными входными данными. Хороший алгоритм генерации кода старается минимизировать сумму стоимостей команд, выполняемых целевой программой для типичных входных данных. Мы увидим, что в некоторых ситуациях для определенных классов регистровых машин возможна генерация оптимального кода для выражений. Глава 8.
Генерация кода 630 8.2.3 Упражнения к разделу 8.2 Упражнение 8.2.1. Сгенерируйте код для следующих трехадресных инструкций в предположении, что все переменные хранятся в ячейках памяти. а)х=1 б)х=а в)х=а+1 г)х=а+Ь д) Две инструкции: х=Ь*с у=а+х Упражнение 8.2.2. Сгенерируйте код для следующих трехадресных инструкций в предположении, что а и Ь вЂ” массивы с элементами, размеры которых равны 4 байт. а) Последовательность из четырех инструкций: х = а[з] у = Ь[з] а[з.] = у Ь[3] = х б) Последовательность из трех инструкций; х = а[э.] = Ь[з.] я=х* в) Последовательность из трех инструкций: х = а[э.] у = Ъ[х] а[э.] = у Упражнение 8.2.3.
Сгенерируйте код для следующих трехадресиых инструкций в предположении, что р и с] располагаются в ячейках памяти: 631 8.2. Целевой язык *Ч Ч=Ч+ *Р = у р=р+4 Упражнение 8.2.4. Сгенерируйте код для следующих трехадресных инструкций в предположении, что х, у и а располагаются в ячейках памяти: ЬТ х < у добо Ь1 а = О досо Ь2 Ь1: а = 1 Упражнение 8.2.5. Сгенерируйте код для следующих трехадресных инструкций в предположении, что и располагается в ячейке памяти: в=О О Ь1: ЬТ 1 > и досо Ь2 Б = Б + 1 Ь = 1 + 1 добо ЬЬ Ь2: Упражнение 8.2.6. Определите стоимость приведенных ниже последовательно- стей команд. а) Ь() КО, у 1Ю К1, а АРВ КО, КО, К1 ЯТ х, КО б) ЬР КО, М()Ь КО, КО, 8 ЬР К1, а(КО) ЯТ Ь, К1 в) 1О КО, с ЬО К1, з.
МШ, К1, К1, 8 ЯТ а(К1), КО г)ЬОКО, р Ь() К1, О(КО) ЯТ х, К1 632 Глава 8. Генерация кода д)1,ОВО, р 10Р1, х ЯТ О(ВО), В1 е) 10 ВО, х В1, у 51)В Ю, ВО, В1 ВЬТЕ *йЗ, ВО 8.3 Адреса в целевом коде В этом разделе мы покажем, каким образом имена в промежуточном представлении могут быть преобразованы в адреса в целевом коде, рассматривая генерацию кода простых вызовов процедур и возвратов из них с использованием статического распределения памяти и выделения памяти в стеке.
В разделе 7.1 было рассказано, что каждая выполняющаяся программа работает в собственном логическом адресном пространстве, которое разбивается на четыре области для кода и данных. 1. Статически определенная область Соде, в которой хранится выполнимый целевой код. 2. Статически определенная область Вайс, в которой хранятся глобальные константы и иные данные, генерируемые компилятором. Размер глобальных констант и данных компилятора также может быть определен в процессе компиляции. 3. Динамически управляемая область памяти Неар для хранения объектов данных, память для которых выделяется и освобождается в процессе выполнения программы. Размер области Неар не может быть определен во время компиляции. 4.
Динамически управляемая область памяти Раск для хранения записей активации между их созданием и уничтожением в процессе вызова процедур и возвратов из них. Как и в случае кучи Неар, размер области %ась не может быть определен во время компиляции. 8.3.1 Статическое выделение памяти Чтобы проиллюстрировать генерацию кода для упрощенных вызовов процедур и возвратов из них, остановимся на следующих трехадресных инструкциях. ° са11 сидее 633 8.3, Адреса в целевом коде ° гегигп ° !та1Г ° асГТоп (заменитель прочих трехадресных инструкций) Размер и размещение записей активации определяется генератором кода на основании информации об именах, хранящейся в таблице символов. Сначала проиллюстрируем, каким образом в записи активации процедуры сохраняется адрес возврата и как передается управление процедуре после ее вызова.
Для удобства будем считать, что в первой ячейке записи активации хранится адрес возврата. Рассмотрим код, необходимый для реализации простейшего случая — статического выделения памяти. Инструкция са11 саПее в промежуточном коде может быть реализована последовательностью двух команд целевой машины: ЯТ са!!ееацайсАгеа, $ЪЬеге + 20$ ВН саПее.садеАгеа Команда ЯТ сохраняет адрес возврата в начале записи активации саПее, а ВН передает управление целевому коду вызываемой процедуры. Атрибут перед саПееааайсАгеа представляет собой константу, которая дает адрес начала записи активации саПее, а атрибут саПее.соЫеАгеа представляет собой константу, указывающую адрес первой команды вызываемой процедуры саПее в области СоЫе памяти времени выполнения.
Операнд влеге+ 20 в команде ЯТ представляет собой адрес возврата, т.е. адрес команды, следующий за командой ВВ. Мы считаем, что влеге — адрес текущей команды и что три константы и две команды в вызывающей последовательности составляют 5 слов, или 20 байт. Код процедуры заканчивается возвратом в вызывающую процедуру, за исключением первой процедуры, не имеющей вызывающей ее процедуры. В этом случае конечная команда — НА!.Т, которая передает управление операционной системе. Инструкция геГигп саПее может быть реализована простой командой перехода ВН *саПеедцайсАгеа Она передает управление по адресу, сохраненному в начале записи активации для си Псе. Пример 8.3.
Предположим, что имеется следующий трехадресный код: // Код с асгфоп 1 са11 р асг1оп 2 634 Глава 8. Генерация кода // Код р аст.йоп 3 гетцгп На рис. 8.4 показана целевая программа для данного трехадресного кода. В ней использована псевдокоманда АСТ1014, представляющая последовательность машинных команд для выполнения инструкции ас~йоп, которая, в свою очередь, представляет трехадресный код, не представляющий в настоящий момент для нас никакого интереса. Код процедуры с произвольным образом начинается с адреса 100, а процедуры р — с адреса 200. Считаем также, что каждая команда АСТ101ч занимает 20 байт. Затем предположим, что память, необходимая для записи активации для этих процедур, статически выделяется начиная с ячеек соответственно 300 и 364. 200: АСТ10Нз 220: ВН *364 д 300-363 хранит запись активации с // Адрес возврата // Локальные данные с 300: 304: // 364-451 хранит запись активации р // Адрес возврата // Локальные данные р 364: 368: Рис.
8.4. Целевой код статического распределения Команды, начинающиеся с адреса 100, реализуют инструкции астйоп>; са11 р; ас~1опз; 1та1~ первой процедуры с. Таким образом, выполнение программы начинается с команды АСТ10И~ по адресу 100. Команда ЯТ по адресу 120 сохраняет адрес возврата 140 в поле состояния машины, которое представляет собой первое слово 100: АСТ10Мз 120: ЯТ 364, $140 132: ВН 200 140: АСТ10Нз 160: НАВТ // Код с // Код ассз.оп~ // Сохранение адреса возврата 140 в ячейке 364 // Вызов р // Возврат в операционную систему // Код р // Возврат к адресу, сохраненному в ячейке 364 635 8.3. Адреса в целевом коде записи активации р. Команда ВН по адресу !32 передает управление первой команде в целевом коде вызываемой процедуры р. После АСТ10Мз выполняется команда перехода по адресу 220.
Поскольку в ячейке по адресу 364 вызывающей последовательностью записан адрес 140, при выполнении команды ВН по адресу 220 операнд *364 представляет собой этот адрес. Таким образом, по завершении процедуры р управление возвращается по адресу 140 и продолжается выполнение процедуры с. о 8.3.2 Выделение памяти в стеке 7/ Инициализация стека ВВ ЯР, йз!ас7сЯ!аг! Код первой процедуры НАВТ Последовательность вызова процедуры увеличивает значение ЯР, сохраняет адрес возврата и передает управление вызываемой процедуре: А171Э ЯР, ЯР, ЬсаИекгесогййяе ЯТ 0(ЯР), ййеге + 16 ВН саПее. со!7еАгеа !! Увеличение указателя стека !! Сохранение адреса возврата !! Передача управления вызываемой !! процедуре Операнд Уса!!еггесолБ!яе представляет размер записи активации, так что команда АВВ делает регистр ЯР указывающим на следующую запись активации. Операнд Статическое распределение может стать выделением памяти в стеке при использовании в записи активации относительных адресов.
Однако в случае стека положение записи активации процедуры во время компиляции неизвестно. Это положение обычно хранится в регистре, так что обратиться к словам в записи активации можно с использованием смещения относительно значения в этом регистре. Для этой цели вполне подходит индексированный режим адресации. Относительные адреса в записи активации могут быть, как говорилось в главе 7, смешениями относительно любой известной позиции в записи активации. Для удобства мы будем использовать положительные смещения, храня в регистре ЯР указатель на начало записи активации на вершине стека. При вызове процедуры вызывающая процедура увеличивает значение ЯР и передает управление вьыываемой процедуре. После того, как управление возвращается в вызывающую процедуру, она уменьшает значение ЯР, тем самым освобождая память, выделенную для записи активации вызываемой процедуры.
Код первой процедуры инициализирует стек, устанавливая ЯР на начало области стека в памяти: 636 Глава 8. Генерация кода №Ьеге + 16 в команде ЯТ представляет собой адрес команды, следующей за командой ВК; он сохраняется по адресу, на который указывает БР. Последовательность возврата состоит из двух частей. Вызываемая процедура передает управление по адресу возврата командой о' Возврат в вызывающую процедуру ВВ *О(БР) Причина использования операнда *О (ЯР) в команде ВВ в том, что нам требуется два уровня косвенности: 0 ( ЯР) — адрес первого слова в записи активации, а *О ( БР ) — хранящийся там адрес возврата. Вторая часть последовательности возврата находится в вызывающей процедуре и заключается в уменьшении ЯР и восстановлении его предыдущего значения, так что после выполнения вычитания ЯР указывает на начало записи активации вызывающей процедуры: ЯОВ БР, ЯР, №саПеггесогг(о(ке о' Уменьшение указателя стека В главе 7 более подробно рассмотрены как вызываюшие последовательности, так и разделение задач между вызывающей и вызываемой процедурами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
