А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 141
Текст из файла (страница 141)
Однако для внутренних узлов с метками й > т мы должны работать с каждой стороной дерева отдельно и сохранять результат большего поддерева. Этот результат затем загружается из памяти непосредственно перед вычислением Х, и на последнем шаге мы работаем с регистрами Л, ~ и Л . Базовый алгоритм модифицируется следующим образом. 1. Узел М имеет как минимум один дочерний узел с меткой т или выше.
Выбираем больший дочерний узел (любой, если их метки одинаковы) как "большой", а оставшийся — как "маленький". 2. Рекурсивно генерируем код для большого дочернего узла с использованием базы 6 = 1. Результат вычислений будет находиться в регистре Л„. 3. Генерируем машинную команду ЯТ 1ы Л„где 1ь — временная переменная, используемая для вычисления узлов с меткой Й.
4. Генерируем код для маленького дочернего узла следующим образом. Если маленький узел имеет метку г или ббльшую, выбираем 6 = 1. Если метка маленького узла 1 ( г, то выбираем базу 6 = г — ~. Затем рекурсивно применяем этот алгоритм к маленькому узлу; результат вычислений будет находиться в регистре Л,. 5. Генерируем команду БР Л,, 1ь.
6. Если большой узел является правым дочерним узлом Ю, генерируем ко- манду ОР Л,,Л,Л ~, если желевым — команду ОР Л,Л ыЛ . и Пример 8.27. Вновь обратимся к выражению, представленному на рис. 8.23, но теперь будем считать, что т = 2, т.е. что для хранения временных значений при вычислении выражения у нас есть только два регистра — й1 и й2. При применении алгоритма 8.26 к рис.
8.23 мы видим, что корень имеет метку 3, большую, чем г = 2. Таким образом, нам надо идентифицировать один из дочерних узлов как "большой". Поскольку у обоих дочерних узлов метки одинаковы, можно выбрать в качестве большого любой. Предположим, что нами выбран правый узел. Поскольку метка большого дочернего узла равна 2, регистров для его вычисления достаточно. Поэтому к данному поддереву применяем алгоритм 8.24 с 6 = 1 и двумя регистрами. Результат выглядит очень похожим на показанный на рис. 8.24, но с регистрами й1 и й2 вместо К2 и КЗ: ь11 к2, с1 БП К3, с Д1И К2, В1, й2 б94 Глава 8.
Генерация кода ВР Р1, е МРР К2, й1, В2 Теперь, поскольку для вычисления левого дочернего узла корня нам нужны оба регистра, генерируем команду ЯТ сЗ, В2 Приступим к левому дочернему узлу корня. Здесь вновь регистров хватает для вычислений, так что генерируется код 1Р В2, Ь РР К1, а ЯРВ Р2, В1, В2 И наконец загружаем временное значение правого поддерева корня при помощи команды 1Р Р1, сЗ и выполняем операцию в корне дерева с помощью команды АРР К2, К2, В1 Полностью последовательность команд показана на рис. 8.25. Рис. 8.25. Оптимальный кол лля дерева иа рис. 8.23, использующий только лва регистра 8.10.4 Упражнения к разделу 8.10 Упражнение 8.10.1.
Вычислите числа Ершова для следующих выражений: а) а/(6 + с) — д * (е + )'); Ы) РР АРР РР М1Л ЯТ РР РР ЯРВ ЬР АРР К2, с1 К1, с В2, Р1, В2 В1, е А2, В1, А2 сЗ, В2 К2, Ь К1, а В2, В1, В2 В1, сЗ К2, В2, К1 8.11. Генерация кода с использованием динамического программирования 695 б) а+ 6*(с*(И+ е)); в) ( — а + яр) к ((6 — *у) (( — с+ в )). Упражнение 8.10.2. Сгенерируйте оптимальный код с использованием двух ре- гистров для каждого выражения из упражнения 8.10.1. Упражнение 8.10.3. Сгенерируйте оптимальный код с использованием трех ре- гистров для каждого выражения из упражнения 8.10.1.
Упражнение 8.10.4. Обобщите вычисление чисел Ершова для деревьев выраже- ний со внутренними узлами с тремя и более дочерними узлами. Упражнение 8.10.5. Присваивание элементу массива, такое как а [ з ) =х, кажется имеющим трн операнда: а, 1 н т. Каким образом можно модифицировать схему дерева с метками для генерации оптимального кода для нашей модели машины? Упражнение 8.10.6.
Исходно числа Ершова использовались на машине, у которой правый операнд выражения мог располагаться в памяти, а не в регистре. Каким образом можно модифицировать схему дерева с метками для генерации оптимального кода для этой модели машины? Упражнение 8 10.7. Некоторые машины требуют двух регистров для некоторых значений однократной точности. Предположим, что результат умножения величин, для хранения которых требуется по одному регистру, размещается в двух смежных регистрах, а при делении а/б значение а должно находиться в двух смежных регистрах. Каким образом можно модифицировать схему дерева с метками для генерации оптимального кода для этой модели машины? 8.11 Генерация кода с использованием динамического программирования Алгоритм 8.26 из раздела 8.10 генерирует оптимальный код из дерева выражения за время, линейно зависящее от размера дерева.
Эта процедура работает для машин, у которых все вычисления выполняются в регистрах, а команды состоят из операторов, применяемых к двум регистрам или к регистру и ячейке памяти. Для расширения класса машин, для которых возможно построение оптимального кода на основе деревьев выражений за линейно зависящее от размера дерева время, можно воспользоваться алгоритмом на основе динамического программирования. Алгоритм динамического программирования может использоваться для генерации кода для любой машины с г взаимозаменяемыми регистрами КО, В1,..., Вг — 1 и командами загрузки, сохранения и операций.
Для простоты мы полагаем, 696 Глава 8. Генерация кода что стоимость любой команды равна единице, хотя алгоритм динамического программирования можно легко модифицировать для случая, когда каждая команда обладает собственной стоимостью. 8.11.1 Последовательные вычисления Алгоритм динамического программирования разбивает задачу генерации оптимального кода для выражения на подзадачи генерации оптимального кода для подвыражений исходного выражения.
В качестве простого примера рассмотрим выражение Е вида Е1 + Ез. Оптимальная программа для Е образуется путем комбинации оптимальных программ для Е1 и Ез в том или ином порядке, за которой следует код вычисления оператора +. Подзадачи генерации оптимального кода для Е1 и Ез решаются аналогично. Оптимальная программа, порожденная алгоритмом динамического программирования, имеет важное свойство, заключающееся в том, что она вычисляет выражение Е = Е| ор Ез "последовательно".
Чтобы понять, что это означает, можно рассмотреть синтаксическое дерево Т для Е. Т2 Здесь Т1 и Тз — деревья для Е1 и Ез соответственно. Мы говорим, что программа Р вычисляет дерево Т последовательно (соп68цоЫу), если она вначале вычисляет те поддеревья Т, которые должны быть вычислены в память. Затем программа вычисляет оставшуюся часть Т либо в порядке Ты Тз н затем корень, либо — Тз, Т1 и затем корень. В любом случае при необходимости используются предварительно вычисленные значения, хранящиеся в памяти.
В качестве примера непоследовательного вычисления Р сначала можно вычислить часть Ты оставив полученное значение в регистре, а не в памяти, затем вычислить Тз и вновь возвратиться к оставшейся части Т,. Можно доказать, что для регистровой машины из данного раздела для любой программы Р, вычисляющей дерево выражения Т, можно найти эквивалентную программу Р', такую, что 1) стоимость Р' не больше стоимости Р; 2) Р' использует не больше регистров, чем Р; 3) Р' вычисляет дерево последовательно. Из этого результата следует, что каждое дерево выражения можно вычислить оптимальным образом с помощью последовательной программы. 8.11. Генерация кода с использованием динамического программирования 697 Кстати, для машин с четно-нечетными парами регистров не всегда существует оптимальное последовательное вычисление; архитектура х86 использует пары регистров для умножения и вычитания.
Для таких машин можно привести примеры деревьев выражений, по которым оптимальная программа на машинном языке должна вначале вычислить в регистр часть левого поддерева корня, затем — часть правого подцерева, затем — еще одну часть левого поддерева, затем — еще одну часть правого и т.д. Такие осцилляции не требуются для оптимального вычисления какого бы то ни было дерева выражения на машине, используемой в данном разделе. Свойство последовательного вычисления, определенное выше, говорит о том, что для любого дерева выражения Т всегда существует оптимальная программа вычисления, состоящая из оптимальных программ вычисления поддеревьев корня, за которыми следует команда вычисления корня.
Это свойство позволяет нам использовать алгоритм динамического программирования для создания оптимальной программы вычисления Т. 8.11.2 Алгоритм динамического программирования Данный алгоритм состоит из трех фаз. Предполагается, что целевая машина содержит г регистров. !. В восходящем порядке для каждого узла п дерева выражения Т вычисляется массив стоимости С, 1-й элемент которого С Я представляет собой оптимальную стоимость вычисления в регистр поддерева 5 с корнем п, прн условии, что для вычисления доступныг регистров, 1 < г < г. 2. Обход дерева выражения Т с использованием векторов стоимости для определения, какие из поддеревьев Т должны быть вычислены в память. 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
