А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 142
Текст из файла (страница 142)
Обход каждого дерева с использованием векторов стоимости и связанных с ними команд для генерации конечного целевого кода. Первым генерируется код для подцеревьев, вычисляемых в память. Каждая из фаз может быть выполнена за время, линейно пропорциональное размеру дерева выражения. Стоимость вычисления узла п включает загрузки и сохранения, необходимые для вычисления Я с данным количеством регистров.
Она также включает стоимость вычисления оператора в корне Я. Нулевой компонент вектора стоимости— оптимальная стоимость вычисления поддерева Я в память. Свойство последовательного вычисления гарантирует, что оптимальная программа для Я может быть сгенерирована путем рассмотрения комбинаций только оптимальных программ для поддеревьев с корнем Я. Такое ограничение снижает количество случаев, которые необходимо рассмотреть. 698 Глава 8. Генерация кода Для вычисления стоимости С [г] в узле и будем рассматривать команды как правила преобразования дерева, как в разделе 8.9.
Рассмотрим каждый шаблон Е, который соответствует входному дереву в узле и. Изучая векторы стоимости в соответствующих наследниках и, определим стоимости вычисления операндов в листьях Е. Для операндов Е, представляющих собой регистры, рассмотрим все возможные порядки вычислений поддеревьев Т в регистры. Для каждого из рассматриваемых порядков вычисления первое поддерево, соответствующее регистровому операнду, можно вычислить с использованием 1 доступных регистров, второе — - помощью г — 1 и т.д. При подсчете стоимости для узла п добавим стоимость команды, связанной с шаблоном Е.
Значение С [1] в таком случае представляет собой минимальную стоимость среди всех возможных порядков вычис- пения. Векторы стоимости для всего дерева Т могут быть вычислены в восходящем порядке (снизу вверх) за время, линейно зависящее от количества узлов в дереве Т. Команды, используемые для получения наилучшей стоимости С [1] для каждого значения з, удобно хранить в узлах дерева; при этом наименьшая стоимость в векторе корневого узла Т дает минимальную стоимость вычисления Т. Пример 8.28. Рассмотрим машину с регистрами ВО и В1 и со следующими ко- мандами, каждая из которых имеет единичную стоимость: 1Ю Вг, М) ор н1, Ы, Р.1 ор В1, В', М1 1О Вг, й) ЯТ М), В) // // // // // Ы = Мз Вг = Вг ор Ву Вг = И ор М1' Ж = В) Мг = В1 Здесь Ы представляет собой либо ВО, либо 81, а М) — адрес в памяти.
Оператор ор соответствует арифметическому оператору. Применим алгоритм динамического программирования, чтобы сгенерировать оптимальный код для синтаксического дерева, приведенного на рис. 8.26. В первой фазе алгоритма мы вычисляем векторы стоимости, показанные около каждого узла. Чтобы проиллюстрировать вычисление стоимости, рассмотрим вектор стоимости у листа а. С (О], стоимость вычисления а в память, равна нулю, поскольку а и так находится в памяти. Стоимость С [1] вычисления а в регистр равна 1, поскольку мы можем загрузить это значение в регистр с помощью одной команды ЬР ВО, а. С [2], стоимость загрузки а в регистр при двух доступных регистрах, та же, что и при одном.
Таким образом, вектор стоимости в листе а представляет собой (0,1,1). Рассмотрим вектор стоимости в корне. Сначала мы определяем минимальную стоимость вычисления корня при одном или двух доступных регистрах. Поскольку корень помечен оператором +, корню соответствует машинная команда 8. !!. Генерация кода с использованием динамического программирования 699 <о, <, !) Рнс. 8.26. Синтаксическое дерево лля (а-Ь) +с* (с)/е) с векторами стоимости в каждом узле АРР КО, КО, М.
При использовании этой команды минимальная стоимость вычисления корня с одним доступным регистром представляет собой сумму минимальной стоимости вычисления правого поддерева в память, минимальной стоимости вычисления левого поддерева в регистр и еще одной единицы для команды сложения. Других способов вычисления нет. Векторы стоимости правого и левого потомков корня показывают, что минимальная стоимость вычисления корня при одном доступном регистре равна 5 + 2 + 1 = 8. Теперь рассмотрим минимальную стоимость вычисления корня с двумя доступными регистрами. Здесь возможны три варианта, зависящие от того, какая из команд используется для вычисления корня и в каком порядке вычисляются левые и правые поддеревья. 1.
Вычисляем левое поддерево в регистр КО при двух доступных регистрах; после этого вычисляем правое поддерево в регистр К1 при одном доступном регистре и для вычисления корня используем команду АРР КО, КО, К).. Такая последовательность действий имеет стоимость 2 + 5 + 1 = 8. 2. Вычисляем правое поддерево в регистр К1 при двух доступных регистрах; после этого вычисляем левое поддерево в регистр КО при одном доступном регистре и для вычисления корня используем команду АРР КО, КО, К1. Такая последовательность действий имеет стоимость 4 + 2+ 1 = 7.
3. Вычисляем правое поддерево в память по адресу М, вычисляем левое поддерево в регистр КО при двух доступных регистрах и для вычисления корня применяем команду АРР КО, КО,М. Такая последовательность действий имеет стоимость 5 + 2 + 1 = 8. Второй вариант дает минимальную стоимость, равную 7. Минимальная стоимость вычисления корня в память определяется прибавлением 1 к минимальной стоимости вычисления корня при всех доступных регистрах, т.е. мы вычисляем корень в регистр, а затем сохраняем полученный результат.
Таким образом, вектор стоимости в корне представляет собой (8,8,7). 700 Глава 8. Генерация кода По векторам стоимости мы можем легко построить код путем обхода дерева. Для дерева на рис. 8.26 в предположении доступности двух регистров оптимальный код имеет следующий вид: иш аО, йО, й1 10 й1, а ЗОВ й1, й1, ъ // а1 = й1 — ь // а1 = а1 + йО АОО а1, В1, но Методы динамического программирования использовались в ряде компиляторов, включая вторую версию переносимого компилятора С, РСС2. Такая методика упрощает перенос на другую целевую машину в силу применимости методов динамического программирования для широкого класса машин. 8.11.3 Упражнения к разделу 8.11 Упражнение 8.11.1.
Расширьте схему, представленную на рис. 8.20, стоимостями и используйте динамическое программирование для генерации кода для инструк- ций из упражнения 8.9.1. !! Упражнение 8.11.2. Каким образом можно применить динамическое программирование для генерации оптимального кода на основе ориентированных ациклических графов? 8.12 Резюме к главе 8 + Генерала кода представляет собой завершающую стадию компилятора. Генератор кода отображает промежуточное представление, произведенное начальной стадией (или, при наличии фазы оптимизации кода, оптимизатором) в целевую программу.
+ Выбор команд — процесс выбора команд целевого языка для каждой инструкции промежуточного представления. + Распределение регистнров — процесс принятия решения о том, какие значения промежуточного представления должны храниться в регистрах. Эффективным методом распределения регистров в компиляторе служит раскраска графа. 10 ВО, с 1О й1, с1 01Ч й1, й1, е // йО = с // й1 =с1 // н1 = й1 / е // йО = йО * й1 // а1 = а 8.12.
Резюме к главе 8 + Назначение регистров представляет собой процесс принятия решения о том, в каком регистре должно храниться данное значение промежуточного представления. + Перенастраиеаемым называется компилятор, который может генерировать код для нескольких наборов команд. + Виртуальнал машина представляет собой интерпретатор промежуточного языка — байт-кода, генерируемого для таких языков программирования, как .1ача и Сй.
+ САЛЮС-камныатер обычно представляет собой двухадресную машину с относительно небольшим количеством регистров, несколькими классами регистров и командами переменной длины со сложными режимами адресации. + ЫЯС-камньютер обычно представляет собой трехадресную машину с большим количеством регистров и операциями, выполняемыми над регистрами. + Базовый блок представляет собой максимальную последовательность следующих друг за другом трехадресных инструкций, входить в которую поток управления может только через первую инструкцию последовательности, а выходить — только через последнюю, без останова и ветвления, за исключением, возможно, последней инструкции базового блока.
+ Граф натака — графическое представление программы, в котором узлами графа являются базовые блоки, а ребра графа указывают возможные пути перехода управления между блоками. + Циклам графа потока является сильно связанная область с единственной точкой входа, именуемой входом в цикл. + Представление базового блока в виде ориентированного аииклическага графа является графом, узлы которого представляют инструкции базового блока, и каждый дочерний узел некоторого узла соответствует инструкции, являющейся последним определением операнда, используемого в инструкции узла-родителя.
+ Локальная аптимизаиия представляет собой локально улучшающие код преобразования, которые могут применяться к программе обычно с использованием перемещающегося по коду окна. + Выбор команд может быть выполнен при помощи процесса преобразования дерева, в котором для замощения синтаксического дерева используются 702 Глава 8. Генерация кода шаблоны, соответствующие машинным командам. С правилами преобразования дерева можно связать стоимости и применить динамическое программирование для получения оптимального замещения для определенных классов машин и выражений. + Число Ершовп говорит о том, сколько регистров необходимо для вычисления выражения без сохранения временных значений в памяти.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
