А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 135
Текст из файла (страница 135)
Машинные команды для операций Ддя трехадресной команды, такой как а = у + з, выполняются следующие действия. 1. Используем функцию легйед (х = у + з) для выбора регистров для х, у и г. Назовем их Л, Л и Л,. 2. Если у не находится в Л (согласно дескриптору регистра для Лк), то генерируем команду 1ЛЭ Лю р', где у' — местоположение р в памяти (в соответствии с дескриптором адреса для у). 3. Аналогично, если з находится не в регистре Л„ то генерируем команду 1.Р Л„ з', где з' — местоположение г. 4. Генерируем команду АИ) Л,, Л ., Л,.
Машинные команды для инструкций копирования Имеется важный частный случай — трехадресная инструкция копирования вида х = у. Мы считаем, что функция легйел всегда выбирает одни и те же регистры как для х, так и для у. Если у еще не находится в регистре Л„, то генерируем машинную команду Ь|э Л„, у. Если же у уже находится в регистре Лю то не делаем ничего. Все, что необходимо сделать, — это обновить дескриптор регистра для Ля так, чтобы он включал х как одно из находящихся в нем значений.
Завершение базового блока Как уже говорилось, переменные, используемые блоком, могут находиться только в регистрах. Если это переменная, временно используемая только внутри блока, то все в порядке, — когда блок завершается, мы можем просто забыть об этой переменной и считать регистр пустым. Однако если при выходе нз блока переменная живая или нам неизвестно, какие переменные живые при выходе нз блока, то следует считать, что значение этой переменной потребуется позже.
В этом случае для каждой переменной х, дескриптор адреса которой не гласит, что ее значение хранится в ячейке памяти, выделенной для .г, требуется генерация команды БТ х, Л, где Л вЂ” регистр, в котором находится значение х в конце базового блока. 663 8.6. Простой генератор кода Управление дескрипторами регистров и адресов При генерации алгоритмом команд загрузки, сохранения н прочих машинных команд необходимо обновление дескрипторов регистров и адресов. Вот правила такого обновления. 1. Для команды 1.Р Л,х: а) изменяем дескриптор регистра Л так, чтобы он указывал, что в Л хранится только переменная т; б) изменяем дескриптор адреса для а, добавляя регистр Л как дополнительное местоположение.
2. Для команды ЯТ и, Л изменяем дескриптор адреса для х, чтобы он включал местоположение переменной в памяти. 3. Для операции, такой как А1зВ Л, Л„, Л„реализующей трехадресную команду х = у+ ж а) изменяем дескриптор регистра для Л так, чтобы он указывал, что в Л хранится только переменная а; б) изменяем дескриптор адреса для х так, чтобы он указывал, что единственное местоположение этой переменной — регистр Л (обратите внимание, что теперь ячейки памяти, выделенные для х, не входят в дескриптор адреса для а); в) удаляем Л из дескрипторов адресов всех переменных, кроме х.
4. При обработке инструкции копирования х = у после генерации при необходимости загрузки у в регистр Лк и после изменения дескрипторов, как того требует инструкция загрузки (правило 1), а) добавляем х в дескриптор регистра Л„; б) изменяем дескриптор адреса для а так, чтобы он указывал, что единственное местоположение этой переменной — регистр Л'„. Пример 8.16. Транслируем базовый блок, состоящий из трехадресных инструкций с=а-ь ц=а — с зг=б+ц а = с1 с1 = зг + ц 664 Глава 8. Генерация кода Мы считаем, что с, и и хт — временные переменные, локальные для данного блока, в то время как а, Ь, с и д — переменные, живые при выходе из блока.
Поскольку мы еще не рассматривали работу функции рейер, будем просто считать, что у нас столько регистров, сколько нам нужно, но что, когда значение регистра более не нужно (например, в нем хранится временная переменная, все использования которой позади), такой регистр используется повторно. Все сгенерированные машинные команды показаны на рис. 8.16. Там же показаны дескрипторы регистров и адресов до и после трансляции каждой трехадресной команды. Вт Ва ВЗ а Ь с С Е::ГЛ::З ГсГЕГа Ы1..Л:.Л.:2 с=а-Ь РО В1, а ОО В2, Ь ЯОВ В2, В1, В2 Г:1'ЛЛ ГОВОРИТ.З.',~.,'.Т Г.З с=а-с ьовз, с ЯОВ В1, Вт Т Г Е:1З вЂ” и ДОО ВЗ, В2, В1 Г....ГГГ,З Г.З. т.:..Л.2З..ГГО1 а г а 'Р В2, С Ггтяызл В1 ВЗ х1=ча и ВОО Ш, ВЗ, В1 г л:л л Выход Ят а, Вз ят с, в1 à — Гт.о Гнг ° Г Каг 1 ГОЗ Рис.
8.16. Сгенерированные команды и изменения в дескрипторах регистров и адресов Для первой трехадресной команды, ~ = а — Ь, необходимо сгенерировать три команды, поскольку изначально в регистрах не находятся никакие значения. Таким образом, а и Ь загружаются в регистры 21 и В2 и значение С вычисляется в регистр й2. Заметим, что мы используем регистр К2 для переменной ~, поскольку значение Ь, находившееся ранее в Р.2, больше в блоке не используется.
Поскольку переменная Ь живая на выходе из блока, то, если бы она не 665 8.6. Простой генератор кода находилась в своей ячейке памяти (на что указывает ее дескриптор адреса), нам потребовалось бы сначала сохранить значение регистра В2 в памяти, отведенной для переменной Ь. Такие решения принимаются функцией деНе~.
Вторая команда, ц = а — с, не требует загрузки а, поскольку данное значение уже находится в регистре В1. Далее, можно использовать регистр В1 для результата операции ц, поскольку значение а, ранее располагавшееся в этом регистре, больше внутри блока не используется, и если а потребуется вне блока, то ее значение имеется в отведенном ей месте в памяти. Обратите внимание на изменения в дескрипторе адреса для а, отражающие тот факт, что а больше не находится в В1, а только в ячейках памяти, выделенных для переменной.
Третья команда, ч = с + ц, требует только одного сложения. Далее, для результата ч можно использовать регистр ВЗ, поскольку значение с, хранящееся в этом регистре, больше внутри блока не требуется, а актуальное значение с хранится в памяти, выделенной для данной переменной. Команда копирования а = б требует загрузки б, поскольку это значение находится только в памяти. Мы указываем, что в регистре В2 теперь хранятся и с1, и а.
Добавление а в дескриптор регистра является результатом обработки инструкции копирования, но не результатом какой-либо машинной команды. Пятая команда, с1 = ч + ц, использует два значения, находящиеся в регистрах. Поскольку ц — временная переменная, значение которой больше не нужно, мы выбираем повторное использование регистра В1 для хранения нового значения переменной б.
Обратите внимание, что теперь с) хранится только в регистре й1, но не в выделенной для этой переменной памяти. То же самое можно сказать и об а, значение которой находится в регистре В2, но не в ячейке памяти для а. В результате нам требуется добавление к машинному коду базового блока, которое сохранит живые переменные а и В в их ячейках памяти. Это — две последние машинные команды базового блока.
о 8.6.3 Разработка функции уеЖеу Наконец, рассмотрим, как реализовать функцию деглед(1) для трехадресной команды 1. Имеется много вариантов, как это сделать, при наличии строжайшего требования, что выбор не должен привести к некорректному коду из-за потери одной или нескольких живых переменных. Начнем наше рассмотрение с операции, в качестве обобщенного примера которой выберем х = у + г. Сначала выбираем регистр для у и регистр для г. Оба выбора выполняются одинаково, так что рассмотрим выбор регистра Л для у. Вот как это делается. Е Если у в настоящее время хранится в регистре, то в качестве Вя выбирается регистр, который уже содержит у. 666 Глава 8. Генерация кода 2.
Если у не хранится в регистре, но имеется регистр, в настоящий момент являющийся пустым, он выбирается в качестве регистра Лю 3. Наиболее сложный случай, когда у не находится в регистре и в настоящий момент пустых регистров нет. Нам в любом случае надо выбрать один из доступных регистров, так что мы должны обеспечить безопасность повторного использования регистра. Пусть Л вЂ” регистр-кандидат, и предположим, что е — одна из переменных, о которых дескриптор регистра Л говорит, что они хранятся в данном регистре. Мы должны убедиться, что значение и в действительности более не требуется, либо значение о можно получить из другого места. Вот возможные ситуации.
а) Если дескриптор адреса для п гласит, что и располагается где-то вне Л, то все в порядке, Л можно использовать. б) Если и представляет собой х — переменную, вычисляемую командой 1, и х не является одновременно одним из операндов команды 1 (в данном примере — з), то все в порядке, Л можно использовать. В этом случае мы знаем, что данное значение х больше не будет использовано, так что его можно игнорировать. в) В противном случае, если и больше не используется (те. после команды 1 нет иных использований о, и если и — живая переменная на выходе из блока, то п вычисляется позже в блоке), то все в порядке, Л можно использовать.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
