А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 131
Текст из файла (страница 131)
Мктод: сначала мы определяем команды промежуточного кода, являющиеся лидерами Пеадег), т.е. первыми командами в некоторых базовых блоках. Команда сразу после окончания промежуточной программы в лидеры не включается. Вот правила поиска лидеров. 1. Первая трехадресная команла промежуточного кода является лидером.
2. Любая команда, являющаяся целевой для условного или безусловного перехода, является лидером. 3. Любая команда, следующая непосредственно за условным или безусловным переходом, является лидером. 642 Глава 8. Генерация кода Затем базовый блок каждого лидера определяется как содержащий самого лидера и все команды до (но не включая) следующего лидера или до конца промежуточной программы. и Пример 8.6.
Промежуточный код на рис. 8.7 превращает матрицу 10 х 10 в единичную. Хотя происхождение этого кода не важно, он может быть результатом трансляции псевдокода на рис. 8.8. При генерации промежуточного кода предполагается, что элементы массива являются числами с плавающей точкой и имеют размер 8 байт, и что матрица хранится построчно. Рис. 8.7. Промежуточный код для установки матрицы 10 х 10 равной единичной Рог г' от 1 до 10 до (ог7 от!до 1Опо а((,Я=00; (ог 1 от 1 до 10 до а(г, г] = 1.0; Рис. 8.8. Исходный код для промежуточного представления на рис. 8.7 Команда 1 является лидером в соответствии с правилом 1 алгоритма 8.5.
Чтобы найти других лидеров, мы сначала находим команды переходов. В данном примере имеются три такие команды — 9, 11 и 17. В соответствии с правилом 2 целевые команды этих переходов являются лидерами; это команды 3, 2 и 13 соответственно. 1) 2) 3) 4) 5) б) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 1 1 ~1 = 10 * з. с2 = 11 + с3 = 8 * Г2 с4 = с3 — 88 а(с4) = 0.0 3=3+1 1й 3 <= 10 алого (3) 1 = 1 + 1 1й 1 <= 10 досо (2) з. = 1 с5 = 1 — 1 гб = 88 * ~5 а[~6) = 1.0 = 1 + 1 1Й х <= 10 досо (13) 643 8.4. Базовые блоки и графы потоков В соответствии с правилом 3 каждая команда, следующая за переходом, является лидером; это команды 1О и !2.
Заметим, что в этом коде нет команд, следующих за командой 17, но если бы такая команда была, то команда 18 также была бы лидером. В результате мы заключаем, что лидерами являются команды 1, 2, 3, 10, 12 и 13. Базовые блоки каждого лидера содержат все команды от него самого до команды перед следующим лидером включительно. Таким образом, базовый блок лидера 1 состоит только из одной команды 1, блок лидера 2 — из одной команды 2.
Блок лидера 3 состоит из команд 3 — 9 включительно. Командами блока лидера 1О являются команды 1О и 11. Блок лидера !2 состоит из единственной команды 12, а в блок лидера 13 входят команды 13-17. и 8.4.2 Информация о дальнейшем использовании Для генерации хорошего кода необходима информация о том, когда значение переменной будет использовано в следующий раз. Если значение переменной, в настояший момент находяшееся в регистре, в дальнейшем использоваться не будет, то этот регистр можно назначить другой переменной. Использование имени в трехадресной инструкции определяется следующим образом.
Предположим, что трехадресная команда ! присваивает значение переменной х, Если команда 7' имеет х в качестве операнда и управление может перейти от ! к !' по пути, на котором нет промежуточных присваиваний к, то мы говорим, что команда 7' использует значение л, вычисленное в команде г. Мы также говорим, что л "живая", или "активная" (1Ые) в команде г. Для каждой трехадресной инструкции г = у + л мы хотим определить следующие использования х, 8 и л. Пока что мы не будем рассматривать использования вне базового блока, содержащего эту трехадресную инструкцию. Наш алгоритм для определения информации о живучести и последующем использовании выполняет обратный проход по каждому базовому блоку.
Информация сохраняется в таблице символов. Можно легко сканировать поток трехадресных инструкций для поиска окончаний базовых блоков, как в алгоритме 8.5. Поскольку процедуры могут иметь произвольные побочные эффекты, для удобства мы считаем, что вызов каждой процедуры начинает новый базовый блок. Алгоритм 8.7. Определение информации о живучести и последующем использовании для каждой инструкции базового блока Вход: базовый блок трехадресных инструкций В.
Считаем, что изначально таблица символов указывает все не временные переменные в блоке В, которые остаются живыми на выходе из блока. Выход: в каждой инструкции 1: х = у+ з в блоке В к значению ! добавляется информация о живучести и последующем использовании л, у и г. 644 Глава 8.
Генерация кода МЕтод: начинаем с последней инструкции В и сканируем блок к началу. В каждой инструкции ~: х = у+ з в блоке В мы делаем следующее. !. Добавляем к инструкции г информацию о живучести и последующем использовании х, у и г, найденную в таблице символов.
2. Устанавливаем в таблице символов т, как "не живая" и "не используемая в дальнейшем", 3. Устанавливаем в таблице символов у и з как "живые", а в качестве последующего их использования указываем г'. Здесь символ + использован просто как оператор. В трехадресной инструкции ~' вида х = +у или х = у все шаги будут те же, что и выше, просто в них игнорируется з. Заметим, что порядок шагов (2) и (3) не может быть изменен, поскольку х может выступать в роли у или з. и 8.4.3 Графы потоков После того как программа разбита на базовые блоки, поток управления между ними представляется в виде графа. Узлами графа потока являются базовые блоки.
Ребро из блока В в блок С идет тогда и только тогда, когда первая команда блока С может следовать непосредственно за последней командой блока В. Имеются две ситуации, когда могут существовать такие ребра. ° Существует условный или безусловный переход от конца блока В к началу блока С. ° С следует непосредственно за В в исходном порядке трехадресных команд, а блок В не заканчивается безусловным переходом. Мы говорим, что  — предшественник С, а С вЂ” преемник В. Зачастую к графу добавляются два узла, именуемые входом и выходом и не соответствующие выполнимым промежуточным командам. Существует ребро от входа к первому выполнимому узлу графа, т.е.
к базовому блоку, который начинается с первой команды промежуточного кода. Если последняя команда программы не является безусловным переходом, то выходу предшествует блок, содержащий эту последнюю команду программы. В противном случае таковым предшествующим блоком является любой базовый блок, имеющий переход к коду, не являющемуся частью программы. Пример 8.8. Множество базовых блоков, построенное в примере 8.6, дает граф потока, показанный на рис. 8.9.
Вход указывает на блок Вы поскольку именно блок В1 содержит первую команду программы. Единственным преемником блока 645 8,4. Базовые блоки и графы потоков в, Рис. 8.9. Граф потока лля рис. 8.7 В> является блок Вз, поскольку В1 не заканчивается безусловным переходом, а лидер Вз следует непосредственно за концом Вз. У блока Вз два преемника.
Одним из них является сам блок Вз, поскольку лидер этого блока — команда 3 — является целевой командой условного перехода 9 в конце блока Вз. Вторым преемником блока Вз является блок В4, поскольку управление из той же команды условного перехода в блоке Вз может быть передано лидеру блока Ва. На выход из графа потока указывает только базовый блок Вв, поскольку единственный путь к коду, следующему за программой, для которой мы строим граф потока, следует через условный переход, которым завершается базовый блок Вв.о Глава 8. Генерация кода 8.4.4 Представление графов потоков Обратите внимание, как на рис. 8.9 в графе потока переходы к номерам команд или меткам заменены переходами к базовым блокам.
Вспомните, что любой условный или безусловный переход выполняется к лидеру некоторою базового блока, и это именно те блоки, которые указаны в командах переходов. Причина такого изменения заключается в том, что обычно после построения графа потока в команды разных базовых блоков вносятся существенные изменения. Если оставить переходы к командам, то придется вносить изменения в целевые адреса переходов всякий раз при изменении даже одной из команд. Графы потоков, будучи обычными графами, могут быль представлены любыми структурами данных, подходящими для представления графов. Содержимое узлов (базовые блоки) требует собственного представления. Содержимое узлов можно представить при помощи указателя на лидера блока в массиве трехадресных команд вместе с количеством команд или указателем на последнюю команду блока. Однако, поскольку внесение изменений может приводить к частому изменению количества команд, пожалуй, более эффективным способом будет создание связанного списка команд для каждого базового блока.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
