А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 140
Текст из файла (страница 140)
с я, л, Рис. 8.22. Набор команд для поиска соответствий Используя наборы строк наподобие показанного в примере 8.22, можно построить программу поиска соответствия деревьям с использованием методов эффективного параллельного поиска строк. На практике переписывание дерева может быть реализовано при помощи поиска шаблонов деревьев в процессе обхода входного дерева в глубину и выполнения сверток при последнем посещении узлов. Учесть стоимости команд можно, связав с каждым правилом преобразования дерева стоимость последовательности машинных команд, генерируемых при применении этого правила.
В разделе 8. ! ! мы рассмотрим алгоритм динамического 688 Глава 8. Генерация кода программирования, который можно использовать вместе с поиском соответствия шаблону. При работе алгоритма динамического программирования можно выбрать оптимальную последовательность соответствий с использованием информации о стоимости каждого правила. Может оказаться необходимым отложить принятие решения до того момента, когда будут известны стоимости всех альтернатив. При таком подходе на основании схемы преобразования дерева может быть быстро построен небольшой эффективный генератор кода. Кроме того, алгоритм динамического программирования освобождает разработчика генератора кода от необходимости разрешать конфликты или принимать решения о порядке вычислений. 8.9.6 Упражнения к разделу 8.9 Упражнение 8.9.1. Постройте синтаксические деревья для каждой из следующих инструкций в предположении, что все неконстантные операнды располагаются в ячейках памяти.
а)х=а*Ь+с*с]; б) х[э.] = у[3 ] * х [1с]; в)х=х+1; Воспользуйтесь схемой, представленной на рис. 8.20, для генерации кода для каждой инструкции. Упражнение 8.9.2. Повторите упражнение 8.9.1 с использованием схемы синтаксически управляемой трансляции на рис. 8.21 вместо схемы преобразования дерева.
! Упражнение 8.9.3. Дополните схему преобразования дерева на рис. 8.20, чтобы она была применима к инструкциям тт]з]!е. 1 Упражнение 8.9.4. Как следует изменить преобразование деревьев, чтобы оно стало применимым к ориентированным ациклическим графам? 8.10 Генерация оптимального кода для выражений Если базовый блок состоит из вычисления одного выражения или если мы принимаем, что достаточно генерировать код блока по одному выражению, то можно выбрать регистры оптимальным образом.
В приведенном далее алгоритме представлена схема нумерации узлов в дереве выражения [синтаксическом дереве 689 8.10. Генерация оптимального кода для выражений для выражения), которая позволяет сгенерировать оптимальный код для дерева выражения при наличии фиксированного количества регистров для вычисления зтого выражения. 8.10.1 Числа Ершова Начнем с назначения узлам дерева выражения чисел, которые указывают, сколько регистров требуется для вычисления зтого узла без сохранения временных переменных. Эти числа иногда называют числами Ершова, после того как А. Ершов (А. Егйоч) использовал подобную схему для машин с единственным арифметическим регистром.
В нашей модели мы пользуемся следующими правилами. 1. Все листья имеют метку 1. 2. Метка внутреннего узла с одним дочерним узлом равна метке дочернего узла. 3. Метка внутреннего узла с двумя дочерними равна: а) если метки дочерних узлов различны — наибольшей из меток дочерних узлов; б) если метки дочерних узлов совпадают — метке дочернего узла, увеличенной на 1. Пример 8.23. На рис.
8.23 показано дерево выражения (с опущенными операторами), которое может быть деревом для выражения (а — б) + е х (с + г1) или для соответствуюшего трехадресного кода с1 = а — Ь т2=с+б СЗ = е * Ь2 т4 = 81+ сЗ Каждый из пяти листьев получает метку 1 в соответствии с первым правилом. Затем можно пометить внутренний узел для Ь1 а-Ь, поскольку оба его дочерних узла помечены. Здесь используется правило Зб, так что данный узел получает метку, на 1 ббльшую метки его дочерних узлов, т.е.
2. То же правило применимо и к внутреннему узлу Ь2=с+с1. Теперь можно перейти к узлу сЗ=е*Т2. Его дочерние узлы имеют метки 1 и 2, так что в соответствии с правилом За метка узла сЗ равна максимальной из них, т.е. 2. Наконец, корень — узел для С4=С1+сЗ вЂ” имеет два дочерних узла с меткой 2, так что он получает метку 3. Г Глава 8. Генерация кода 690 Рис. 8.23. Дерево, помеченное числами Ершова 8.10.2 Генерация кода на основе помеченных деревьев выражений Можно доказать, что в нашей модели машины (где все операнды должны располагаться в регистрах и регистры могут использоваться и как операнды, и как результаты операции) метка узла указывает наименьшее количество регистров, необходимое для вычисления выражения без сохранения временных результатов. Поскольку в этой модели мы должны загружать каждый операнд и вычислять результат для каждого внутреннего узла, единственная вещь, которая может сделать код неоптимальным, — изли1пние сохранения временных значений.
Аргументом в пользу этого утверждения служит приведенный далее алгоритм для генерации кода без сохранения временных значений с использованием количества регистров, равного метке корня. Алгоритм 8.24. Генерация кода для помеченного дерева выражения Вход: помеченное дерево, в котором каждый операнд появляется по одному разу (т.е.
отсутствуют общие подвыражения). Выход: оптимальная последовательность машинных команд для вычисления корня в регистр. Метод: приведенный далее рекурсивный алгоритм для генерации машинного кода. Описанные ниже шаги применяются к корню дерева. Если алгоритм применяется к узлу с меткой к, будут использоваться ровно й регистров.
В алгоритме имеется "база" 6 > 1 для используемых регистров, т.е, фактически используемыми регистрами будут Кмйььы..., Ль.ьа и Результат всегда вычисляется в регистр ттььь-и 1. Для генерации машинного кода для внутреннего узла с меткой )е и двумя дочерними узлами с равными метками (которые должны быть равны й — 1) выполняем следующее. 691 8.10. Генерация оптимаяьного кода для выражений а) Рекурсивно генерируем код для правого дочернего узла с базой 6+ 1. Результат правого дочернего узла находится в регистре Вь~ь н б) Рекурсивно генерируем код для левого дочернего узла с базой 6.
Результат левого дочернего узла находится в регистре Йь~ь з. в) Генерируем команду ОР Вь+ь — ы Вь ь — з, Вь,ь и где ОР— операция в рассматриваемом внутреннем узле. 2. Предположим„что у нас имеется внутренний узел с меткой )е и дочерние узлы с разными метками. Тогда один из дочерних узлов, назовем его "большим", имеет метку Й, а второй — "маленький" — некоторую метку т < й. Для генерации кода для этого внутреннего узла с использованием базы 6 делаем следующее. а) Рекурсивно генерируем код для большого дочернего узла с использованием базы 6; результат находится в регистре Ль~ь б) Рекурсивно генерируем код для маленького узла с использованием базы 6; результат находится в регистре Нь+ и Заметим, что, поскольку т < Й, при вычислениях не используются ни регистр Вьгь ы ни какой-либо иной регистр с большим номером. в) Генерируем команду ОР Вь~ь ыйь ыйь~ь ~ или ОР Ва,ь и Ль ь ОЛь~ н в зависимости от того, является большой дочерний узел соответственно правым или левым дочерним узлом.
3. Для листа, представляющего операнд х, при использовании базы 6 генерируем команду ЬО Гга х. о Пример 8.25. Применим алгоритм 8.24 к дереву на рис. 8.23. Поскольку метка корня равна 3, результат будет находиться в регистре ггз, а использоваться при вычислениях будут только регистры Вы ггз и Вз. База для корня — 6 = 1. Поскольку корень имеет два дочерних узла с равными метками, сначала генерируем код для правого дочернего узла с базой 2.
При генерации кода для правою дочернего узла корня с меткой сЗ мы выясняем, что его правый дочерний узел — большой, а левый — маленький. Соответственно, сначала мы генерируем код для правого дочернего узла с базой 6 = 2. Применяя правила для дочерних узлов с одинаковыми метками и для листьев, генерируем следующий код для узла с меткой с2; 1О КЗ, с1 Ю К2,С АОО КЗ, К2, КЗ 692 Глава 8.
Генерация кода Теперь сгенерируем код для левого дочернего узла, который представляет собой узел с меткой е. Поскольку б = 2, генерируется команда ЬР К2, е После этого код для правого дочернего узла корня можно завершить, добавив команду М7Л» КЗ, К2, КЗ Далее алгоритм генерирует код для левого дочернего узла корня, получая результат в регистре Ля и используя базу б = 1. Полностью сгенерированная последовательность команд показана на рис. 8.24. П ЬР КЗ, с) РР К2,С АРР КЗ, К2, ЬР К2, е МЛ КЗ, К2, ЬР К2, Ъ 1Р К1,а ЯРВ К2, К1, йРР КЗ, К2, К2 КЗ Рис.
8.24. Оптимальный код, использующий три регистра, для дерева на рис. 8.23 8.10.3 Вычисление выражений ври недостаточном количестве регистров Если количество доступных регистров меньше метки корня дерева, то непосредственно применить алгоритм 8.24 невозможно. Нам потребуется ввести в код несколько команд, которые сбрасывают значения поддеревьев в память, а затем при необходимости загружают их оттуда. Далее приведен модифицированный алгоритм, принимающий во внимание ограниченное количество регистров. Алгоритм 8.26. Генерация кода для помеченного дерева выражения ВхОд: помеченное дерево, в котором каждый операнд появляется по одному разу (т.е.
отсутствуют общие подвыражения) и количество регистров т ) 2. ВыхОд: оптимальная последовательность машинных команд для вычисления кор- нЯ в РегистР с использованием не более чем г РегистРов (РегистРы Въ Вз,..., )т,). МетОд: приведенный далее рекурсивный алгоритм для генерации машинного ко- да. Описанные ниже шаги применяются к корню дерева с использованием базы 693 8.10. Генерация оптимального кода для выражений 6 = 1. Для узла Х с меткой г или меньшей алгоритм совпадает с алгоритмом 8.24, и здесь эти шаги описаны не будут.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
