А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 130
Текст из файла (страница 130)
Пример 8.4. Программа на рис. 8.5 представляет собой абстрагированную программу быстрой сортировки из предыдущей главы. Процедура д рекурсивная, так что в один и тот же момент может существовать несколько активаций д. 0 Код гп асг1оп1 са11 с( асг№опз )за1г // Код р асС№опз гебцгп д Код д асгл.оп4 са11 р асг№опа са11 с( асс№опа са11 с( гесцгп Рис. 8.5. Код к примеру 8.4 Предположим, что размеры записей активации для процедур п1, р и с( равны соответственно тз(зе, рясе и дяде.
Первое слово в каждой записи активации 637 8.3. Адреса в целевом коде хранит адрес возврата. Произвольным образом мы полагаем, что коды этих про- цедур начинаются соответственно в адресах 100, 200 и 300 и что стек начинается с адреса 600. Целевая программа показана на рис. 8.6. !00: !08: 128: 136: 144: 152: 160: 180: 00 ЯР, ()600 АСТ1оы, А00 ЯР, ЯР, ()тз/ге ЯТ 0(ЯР), ()152 ВН 300 ЯНВ БР, ЯР, ()тз/ге АСТ1ОНг НАОТ // Код р // Возврат 200: 220: АСТ1ОМз ВВ *0(ЯР) () 9з/ге 344 // Внесение адреса возврата в стек // Вызов р ()дз/ге () дз/ге 396 // Внесение адреса возврата в стек // Вызов 9 () дз/ге ()9з/ге 440 // Внесение адреса возврата в стек // Вызов д ()9з/ге // Возврат // Начало стека Рис.
8.6. Целевой код для выделения памяти в стеке 600: 300: 320: 328: 336: 344: 352: 372: 380: 388: 396: 404: 424: 432: 440: 448: 456: АС Т 1 ОМ4 А00 ЯР, ЯР, ЯТ 0(ЯР), () ВН 200 ЯВВ ЯР, ЯР, АСТ1ОН, А00 ЯР, ЯР, ЯТ 0(ЯР), () ВН 300 Я'о'В ЯР, ЯР, АСт1ОНа А00 ЯР, БР, ЯТ 0(ЯР), () ВВ 300 Б()В ЯР, ЯР, ВН *0(ЯР) // Код т // Инициализация стека // Код асс1оп! // Начало вызывающей последовательности // Внесение адреса возврата в стек // Вызов д // Восстановление ЯР // Код д // Содержит условный переход по адресу 456 638 Глава 8.
Генерация кода Предполагается, что АСТ10М4 содержит условный переход к адресу 456 последовательности возврата из с1; в противном случае рекурсивная процедура с1 будет вечно вызывать саму себя. Пусть глз1ге, рябе и 9з1зе равны соответственно 20, 40 и 60. Первая команда по адресу 100 инициализирует ЯР значением 600, начальным адресом стека. Перед передачей управления от ш к с1 в регистре ЯР хранится значение 620, так как лм1зе равно 20. Далее, когда с1 вызывает р, команда по адресу 320 увеличивает значение ЯР до 690, места, где начинается запись активации р. После возврата управления процедуре г1 значение ЯР снова уменьшается до 620. Если из последующих двух рекурсивных вызовов с1 тут же выполняется возврат, то максимальное значение ЯР в процессе работы равно 680.
Заметим, однако, что последняя использованная ячейка стека — 739, поскольку запись активации для с1 начинается с адреса 680 и занимает 60 байт. и 8.3.3 Адреса имен времени выполнения Стратегия выделения памяти и схема размещения локальных данных в записи активации процедуры определяет, каким образом выполняется обращение к памяти, предназначенной для имен. В главе 6 считается, что имя в трехадресной команде в действительности является указателем на запись в таблице символов для данного имени. Такой подход обладает важным преимуществом; он делает компилятор более переносимым, поскольку не требуется изменение начальной стадии компилятора даже при переносе на другую машину с иной организацией времени выполнения. С другой стороны, генерация конкретной последовательности шагов обращения при генерации промежуточного кода может существенно помочь в случае оптимизирующего компилятора, поскольку обеспечивает компилятор детальной информацией, которой нет в простых трехадресных командах.
В любом случае в конечном счете имена должны быть заменены кодом для доступа к ячейкам памяти. Давайте рассмотрим простую трехадресную инструкцию присваивания х = О. Предположим, что после обработки объявления в процедуре запись для х в таблице символов содержит относительный адрес 12.
Рассмотрим случай, когда х находится в статически выделенной области памяти, начинающейся по адресу згайс. Тогда фактический адрес х времени выполнения равен згаг1с + 12. Хотя в конечном счете компилятор может определить значение згайс+ 12 во время компиляции, позиция статической области может не быть известна, когда генерируется промежуточный код для доступа к имени. В таком случае имеет смысл генерировать трехадресный код для "вычисления" згайс + 12, отдавая себе отчет в том, что это вычисление будет выполнено на стадии генерации целевого кода или, возможно, загрузчиком перед запуском программы. Присваивание х = 0 транслируется в зсаььс1121 = О 639 8.3, Адреса в целевом коде Если статическая область начинается с адреса 100, то целевой код для этой ин- струкции имеет вид 10 112, $0 8.3.4 Упражнения к разделу 8.3 Упражнение 8.3.1.
Сгенерируйте код для следующих трехадресных инструкций в предположении выделения памяти в стеке, причем регистр БР указывает на вершину стека: са11 р са11 Ч гегигп са11 г гесцгп гесигп Упражнение 8.3.2. Сгенерируйте код для следующих трехадресных инструкций в предположении выделения памяти в стеке, причем регистр ЯР указывает на вершину стека. а)х=1 б)х=а в)х=а+ 1 г)х= а+Ь д) Две инструкции: х=Ь*с у = а+ х Упражнение 8.3.3. Сгенерируйте код для следующих трехадресных инструкций в предположении выделения памяти в стеке, а также в предположении, что а и Ь вЂ” массивы элементов, представляющих собой четырехбайтовые значения.
а) Последовательность из четырех инструкций; х = а(1) У = ЬС3) а[1] = у Ь!3) = х Глава 8. Генерация кода 640 б) Последовательность из трех инструкций: х = а(1) = Ь(з) х = х * у в) Последовательность из трех инструкций: х = а[з) у = Ь(х) а(з.) = у 8.4 Базовые блоки и графы потоков В этом разделе вводится представление промежуточного кода в виде графа, полезное при рассмотрении генерации кода (даже если алгоритм генерации кода не строит граф явным образом).
Генерация кода выигрывает от знания контекста. Как мы увидим в разделе 8.8, знание того, какие значения определены и используются, помогает наилучшим образом выполнить распределение регистров; из раздела 8.9 вы узнаете, что просмотр последовательности трехадресных инструкций позволяет наилучшим образом решить задачу выбора команд. Представление строится следующим образом. !. Промежуточный код разделяется на базовые блоки (Ьаз!с Ыоскз), представляющие собой максимальные последовательности следующих друг за другом трехадресных команд, обладающие приведенными ниже свойствами: а) поток управления может входить в базовый блок только через первую команду блока, т.е.
переходы в средину блока отсутствуют; б) управление покидает блок без останова или ветвления, за исключением, возможно, в последней команде блока. 2. Базовые блоки становятся узлами графа ловюка (бои 8гарп), ребра которого указывают порядок следования блоков.
Начиная с главы 9 мы будем рассматривать трансформации графов потоков, которые преобразуют исходный промежуточный код в "оптимизированный" промежуточный код, позволяющий генерировать более качественный целевой код. "Оптимизированный" промежуточный код превращается в машинный код с помощью методов генерации кода из этой главы. 641 8.4. Базовые блоки и графы потоков Влияние прерываний Представление о том, что управление, достигнув начала базового блока, обязательно дойдет до его конца, требует пояснений. Имеется множество причин для прерываний, явно не отражаемых в коде, которые могут заставить управление покинуть блок, возможно, навсегда.
Например, команда наподобие х=у/г кажется не влияющей на поток управления, но если г равно О, то она может привести к завершению программы. Мы не будем беспокоиться о таких возможностях. Причина этого в следующем. Цель построения базовых блоков — оптимизация кода. В общем случае прн генерации исключения либо оно будет обработано и управление вернется к команде, вызвавшей его, как если бы никакого исключения не было, либо программа завершится с кодом ошибки. В последнем случае оптимизация кода не имеет значения, поскольку в любом случае программа не даст требуемого результата.
8.4.1 Базовые блоки Наша первая задача состоит в разбиении последовательности трехадресных команд на базовые блоки. Мы начинаем новый базовый блок с первой команды и добавляем команды до тех пор, пока не встретим условный или безусловный переход или метку у следующей команды. При отсутствии переходов и меток управление последовательно проходит от одной команды к другой. Эта идея формализована в следующем алгоритме. Алгоритм 8.5. Разбиение трехадресных команд на базовые блоки Вход: последовательность трехадресных команл. Выход; список базовых блоков для данной последовательности, в которой каждая команда принадлежит ровно одному базовому блоку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
