А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 134
Текст из файла (страница 134)
Для каждого узла с одной или несколькими связанными переменными мы строим трехадресную инструкцию, которая вычисляет значение одной из этих переменных. Предпочтительно вычисление результата в переменную, которая будет живой при выходе из блока. Однако если глобальная информация о живых переменных отсутствует, то надо считать, что любая переменная программы (но нс временные переменные, генерируемые компилятором для обработки выражений) является живой при выходе из базового блока. Если у узла несколько присоединенных живых переменных, то следует добавить команды копирования, которые присвоят корректное значение каждой из этих переменных.
Иногда глобальная оптимизация позволяет избежать копирования, если одна из двух переменных может быть использована вместо другой. 657 8.5. Оптимизация базовых блоков Пример 8.15. Вернемся к ориентированному ациклическому ~рафу на рис. 8.12. В обсуждении после примера 8.10 мы решили, что если переменная Ь не является живой, то для реконструкции базового блока достаточно трех инструкций: а=Ь+с с1 = а — с1 с=с!+с Третья команда, с = с! + с, должна использовать в качестве операнда с1, а не Ь, поскольку оптимизированный базовый блок никогда не вычисляет Ь. Если при выходе из базового блока живыми являются и Ь, и с1 или если мы не знаем, какие именно переменные живые при выходе из базового блока, то мы должны вычислять как г1, так и Ь. Это можно сделать при помощи последовательности а=Ь+с с! = а — с! Ъ = с! с=с1+с Этот базовый блок все равно остается более эффективным, чем исходный.
Хотя количество инструкций в нем остается тем же, что и в исходном блоке, вычитание заменено копированием, которое на большинстве машин является более выгодной операцией. Далее, при проведении глобального анализа может выясниться, что использования Ь вне блока можно будет заменить использованиями с1. В таком случае позже можно будет вернуться к данному базовому блоку и убрать из него копирование Ъ = г1. Интуитивно это копирование можно устранить, если везде, где используется значение переменной Ь, переменная с1 все еще хранит то же самое значение. Это может быть так, а может и не быть в зависимости от того, когда и как программа заново вычисляет значение с1. с При восстановлении базового блока из ориентированного ациклического графа мы должны не только беспокоиться о том, какие переменные используются для хранения значений узлов ориентированного ациклического ~рафа, но и о порядке, в котором мы перечисляем команды, вычисляюшие значения различных узлов.
Следует помнить следующие правила. ! . Порядок команд должен отражать порядок узлов в ориентированном ациклическом графе, т.е. мы не можем вычислить значение узла до тех пор, пока не вычислим значения всех его дочерних узлов. 2. Присваивания массиву должны следовать за всеми присваиваниями этому массиву или за вычислениями с использованием его элементов, которые в исходном базовом блоке выполняются ранее. 658 Глава 8. Генерация кода 3. Вычисление элементов массива должно следовать за всеми более ранними (в соответствии с исходным базовым блоком) присваиваниями элементам того же массива.
Единственная разрешенная перестановка заключается в том, что два вычисления с использованием элементов одного и того же массива могут быть выполнены в любом порядке, если между ними нет ни одного присваивания элементам этого массива. 4. Любое использование переменной должно следовать за всеми более ранними (в соответствии с исходным базовым блоком) вызовами процедур или косвенными присваиваниями с использованием указателей. 5. Любой вызов процедуры или косвенное присваивание с использованием указателя должно следовать за всеми более ранними (в соответствии с исходным базовым блоком) вычислениями переменных. Иными словами, при переупорядочении кода ни одна инструкция не должна пересекаться с вызовом процедуры или присваиванием с использованием указателя, а использования одного и того же массива могут пересекаться только в том случае, если оба они являются обращениями к массиву, но не присваиваниями значений его элементам.
8.5.8 Упражнения к разделу 8.5 Упражнение 8.5.1. Постройте ориентированный ациклический граф для базового блока с) = Ь * с е=а+Ь Ь=Ь*с а=е — д Упражнение 8.5.2. Упростите трехадресный код из упражнения 8.5. Е в предпо- ложении, что а) а — единственная живая переменная на выходе из блока; б) на выходе из блока живыми являются переменные а, 6 и с. Упражнение 8.5.3.
Постройте ориентированный ациклический граф для кода бло- ка Вв на рис. 8.9. Не забудьте включить в него сравнение 1 < 10. Упражнение 8.5.4. Постройте ориентированный ациклический граф для кода бло- ка Вз на рис. 8.9. Упражнение 8.5.5. Доработайте алгоритм 8.7 так, чтобы он мог обрабатывать трехадресные инструкции вида 659 8,5. Оптимизация базовых блоков а) а[э.] = Ь б) а = Ь[а] в) а = *Ь г)*а=Ъ Упражнение 8.5.6. Постройте ориентированный ациклический граф для базового блока а[э.] = Ь *р = с с[ = а[>] е=*р *р = а[1] в предположении, что а) р может указывать куда угодно; б) р может указывать только на Ь или с[. ! Упражнение 8.5.7. Если выражение с указателем или массивом, такое как а [ з ] или *р, сначала получает значение, а затем используется, причем без возможности изменения в промежутке между этими событиями, то этой ситуацией можно воспользоваться для упрощения ориентированного ациклического графа.
Например, в коде упражнения 8.5.6, поскольку присваивания р между второй и четвертой инструкциями не происходит, инструкцию е = *р можно заменить инструкцией е = с, независимо от того, куда именно указывает р4. Пересмотрите алгоритм построения ориентированного ациклического графа с тем, чтобы он использовал преимущества такой ситуации, и примените этот алгоритм к коду из упражнения 8.5.6. Упражнение 8.5.8.
Предположим, что базовый блок образован инструкциями на языке программирования С х = а + Ь + с + с1 + е + йг у= а+ с+е; а) Приведите трехадресные инструкции [по одному сложению в инструкции) для этого блока. б) Воспользуйтесь коммутативным и ассоциативным законами для того, чтобы этот блок использовал минимально возможное количество команд, в предположении, что и х, и у живые на выходе из блока. 'Лишь бы этот указатель не указывал на о (те. между второй н четвертой инструкциями не должна меняться переменная, на которую указывает р). — Прим. лед. 660 Глава 8. Генерация кода 8.6 Простой генератор кода В этом разделе мы рассмотрим алгоритм генерации кода для отдельного базового блока.
Он поочередно рассматривает трехадресные команды и отслеживает, какие значения находятся в регистрах, так что позволяет избежать излишних загрузок и сохранений. Одним из основных вопросов в процессе генерации кода является принятие решения о том, как наилучшим образом использовать регистры. Существует четыре основных применения регистров. ° В большинстве архитектур некоторые или все операнды должны находиться в регистрах для выполнения операции.
° Регистры представляют собой хорошие временные переменные — места для хранения резулыатов подвыражений при вычислениях больших выражений или, в общем случае, для размещения переменных, использующихся в пределах только одного базового блока. ° Регистры используются для хранения (глобальных) значений, которые вычисляются в одном базовом блоке и используются в других базовых блоках, например, индекса цикла, который увеличивается на каждой итерации цикла и неоднократно используется в пределах цикла.
° Регистры зачастую используются для помощи в управлении памятью времени выполнения, например для управления стеком времени выполнения„ включая поддержку указателя стека и, возможно, элементов на вершине стека. Это конкурирующие использования регистров, поскольку их количество весьма ограничено. Алгоритм в данном разделе предполагает наличие некоторого множества регистров, доступных для хранения использующихся в блоке значений. Обычно это множество не включает в себя все имеющиеся в машине регистры, поскольку некоторые из них зарезсрвированы для глобальных переменных и управления стеком. Мы считаем, что базовые блоки уже преобразованы в идеальные последовательности трехадресных команд при помощи таких трансформаций, как объединение общих подпоследовательностей и др.
Мы также предполагаем, что для каждого оператора имеется ровно одна машинная команда, которая получает необходимые операнды в регистрах и выполняет операцию, причем ее резулыат также находится в регистре. Машинные команды имеют вид ° 1,0 гел, гнея ° ЯТ вет, гея ° ОР ген, гее, ген 661 8.6. Простой генератор кода 8.6.1 Дескрипторы регистров и адресов Наш алгоритм генерации кода поочередно рассматривает каждую трехадресную команду и определяет, какие загрузки необходимо выполнить, чтобы требуемые операнды находились в регистрах.
После генерации загрузок генерируется сама операция, а затем при необходимости сохранения результата в памяти— команды сохранения. Для принятия необходимых решений нужна структура данных, которая говорит нам, какие переменные программы находятся в регистрах и в каких именно регистрах. Нам также надо знать, содержит ли в настоящий момент ячейка памяти для данной переменной корректное значение, — дело в том, что может оказаться так, что новое вычисленное значение переменной находится в регистре и еще не сохранено в памяти. Требуемая структура данных имеет следующие дескрипторы. 1.
Дескриптор регистра отслеживает для всех доступных регистров имена переменных, значения которых хранятся в настоящее время в регистрах. Поскольку мы будем использовать только регистры, доступные для локального использования в базовом блоке, мы полагаем, что изначально все дескрипторы регистров пустые. В процессе генерации кода каждый регистр будет хранить значение нуля или некоторого количества имен. 2. Дескриптор адреса отслеживает для каждой переменной программы местоположение, где можно найти текущее значение этой переменной. Местоположение может быть регистром, адресом памяти, положением в стеке или некоторым множеством из этих данных.
Эта информация может храниться в записи таблицы символов для имени переменной. 8.6.2 Алгоритм генерации кода Важнейшей частью алгоритма является функция деЖсд(У), которая выбирает регистры для каждой ячейки памяти, связанной с трехадресной командой 1. Функция деИед имеет доступ к дескрипторам регистров и адресов для всех переменных базового блока и может также иметь доступ к некоторой полезной информации о потоках данных, такой как переменные, остающиеся живыми при выходе из базового блока. Мы рассмотрим эту функцию после того, как представим основной алгоритм. Пока мы не знаем общее количество регистров, доступных для локальных данных, принадлежащих базовому блоку, мы полагаем, что регистров достаточно для того, чтобы после освобождения всех доступных регистров путем сохранения их значений в памяти можно было выполнить любую трехадресную операцию.
В трехадресной команде наподобие х = у + я мы рассматриваем + как обобщенный оператор, а АРй — как эквивалентную машинную команду. Таким Глава 8. Генерация кода 662 образом, мы не используем коммутативность сложения. Поэтому, когда мы реализуем операцию, значение у должно находиться во втором регистре в команде А00 и никогда в третьем. Возможное усовершенствование алгоритма заключается в генерации кода для х = у + к н х = г + у для коммутативного оператора + н выборе лучшей последовательности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
