Лекция 07. Выбор команд (Лекции (2015)), страница 2

Поэтому соответствия можно искать спомощью LR-анализатора, используемого при синтаксическоманализе1)Ri  ca{ LDRi#a }2)R i  Mx{ LDRix }3)M = Mx Ri{ STx4)M = ind Ri Rj{ ST5)Ri  ind + ca Rj{ LDRi a(Rj)}6)Ri  + Ri ind + ca Rj{ ADDRi Ria(Rj)}7)Ri  + Ri R j{ ADDRi RiRj }8)Ri  + Ri c 1{ INCRi }9)R  sp10)МmRi }*Ri Rj}327.5 Метод переписывания дерева7.5.7 Поиск соответствий с помощью синтаксического анализаНа основе продукций схемы трансляции можно построитьLR-анализатор: стековый автомат, который загоняет символыанализируемой строки в стек (перенос) пока в голове стека неполучится строка, являющаяся правой частью одной изпродукций. Когда это происходит выполняется свертка: праваячасть найденной продукции удаляется из стека и вместо нее встек помещается левая часть этой продукции. При каждойсвертке генерируется машинная команда из соответствующейстроки третьего столбца таблицы.Обычно грамматика генерации кода неоднозначна и поэтомудолжны быть предприняты меры по разрешению конфликтов.При отсутствии информации о стоимости общее правило состоитв предпочтении больших сверток меньшим.Это означает, что в случае конфликта «свертка – свертка»выбирается более длинная свертка, а при конфликте «перенос –свертка» – перенос.

Такой подход обеспечивает выполнениебольшего числа операций с помощью одной машинной команды.337.5 Метод переписывания дерева7.5.7 Поиск соответствий с помощью синтаксического анализаПреимущества использования LR-анализа для генерации кода:Методы синтаксического анализа эффективны и хорошоизучены, использование алгоритмов LR-анализаобеспечивает надежность и эффективность генераторакода.Облегчается перенастройка генератора кода для другойцелевой машины, так как создание генератора кода дляновой машины сводится к разработке грамматики,описывающей ее команды.Качество генерируемого кода может быть сделано весьмавысоким за счет добавления продукций для особыхслучаев, чтобы использовать преимущества машинныхидиом.347.5 Метод переписывания дерева7.5.8 Проверка атрибутовВ схеме трансляции для генерации кода встречаются ограниченияна значения атрибутов.

Такие ограничения могут возникнутьв связи с машинными идиомами.Машинная команда может требовать, чтобы значенияатрибута находились в определенном диапазоне или чтобы двазначения атрибутов были связаны некоторым соотношением.Такие ограничения на значения атрибутов могут быть указаны какпредикаты, проверяемые перед выполнением свертки.Использование предикатов может обеспечить большую гибкостьи простоту описания по сравнению с чисто грамматическойспецификацией генератора кода.Некоторые аспекты архитектуры целевой машины, напримеррежимы адресации, могут быть выражены с помощьюограничений на атрибуты.

Это позволяет сократить описаниецелевой машины.357.5 Метод переписывания дерева7.5.7 Проверка атрибутовВ случае использования обобщенных шаблонов для выборакоманд в частных случаях могут использоваться семантическиепроверкиПример.С помощью одного обобщенного шаблона могут бытьпредставлены два варианта команд сложения: ADD и INC.Для выбора команды используется семантическая проверка.Обобщенный шаблонСемантическая проверка367.6 Генерация оптимального кода для выражений7.6.1 Разметка деревьев выражений. Числа ЕршоваЧисла Ершова назначаются каждому узлу дерева выражения иуказывают, сколько регистров требуется для вычисления этогоузла без сохранения временных переменныхЧисла Ершова назначаются по следующим правилам:1.Все листья имеют метку 1.2.Метка внутреннего узла с одним дочерним узлом равнаметке дочернего узла.3.Метка внутреннего узла с двумя дочерними равна:(а)если метки дочерних узлов различны –наибольшей из меток дочерних узлов;(б)если метки дочерних узлов совпадают –метке дочернего узла, увеличенной на 1.377.6 Генерация оптимального кода для выражений7.6.1 Разметка деревьев выражений.

Числа Ершова Пример. Трехадресный код,соответствующийвыражению(а – b) + е  (с + d):t1t2t3t4====acet1–+*+bdt2t3 можнопредставить в виде деревана верхнем рисунке Разметив узлы этого деревав соответствии сосформулированнымиправилами, получим деревона нижнем рисунке387.6 Генерация оптимального кода для выражений7.6.2Алгоритм генерации кодадля размеченных деревьев выраженийВход: размеченное дерево, в котором каждый операндпоявляется по одному разу (т.е.

отсутствуют общиеподвыражения).Выход: оптимальная последовательность машинных команд длявычисления значения корня в регистре.Метод: рекурсивный алгоритм генерации машинного кода(на следующем слайде).Замечание. Если алгоритм применяется к узлу с меткой k,будут использованы ровно k регистров: Rb, Rb+1, ..., Rb+k-1.Результат всегда будет помещаться в регистр Rb+k-1.397.6 Генерация оптимального кода для выражений7.6.21.Алгоритм генерации кодадля размеченных деревьев выраженийГенерация машинного кода для внутреннего узла сметкой k и двумя дочерними узлами с равными метками(в этом случае метки обоих дочерних узлов равны k – 1):(a)Рекурсивная генерация кода для правогодочернего узла, используя регистры Rb+1, ..., Rb+k-1.Результат правого дочернего узла помещается врегистр Rb+k-1.(b)Рекурсивная генерация кода для левогодочернего узла, используя регистры Rb, ..., Rb+k-2.Результат левого дочернего узла помещается врегистр Rb+k-2.(c)Генерация командыОР Rb+k-1, Rb+k-2, Rb+k-1,где OP – операция в узле с меткой k.407.6 Генерация оптимального кода для выражений7.6.22.Алгоритм генерации кодадля размеченных деревьев выраженийГенерация кода для внутреннего узла с меткой k и двумядочерними узлами с разными метками (в этом случае один издочерних узлов («большой») имеет метку k, а второй(«маленький») – метку т < k):(a)Рекурсивная генерация кода для большого узла,используя k регистров Rb, ..., Rb+k-1;результат получается в регистре Rb+k-1.(b)Рекурсивная генерация кода для маленького узла,используя m регистров Rb, ..., Rb+m-1;результат находится в регистре Rb+m-1.т < k, следовательно при вычислениях не используютсяни регистр Rb+m, ни какой-либо иной регистр с большимномером.(c)Генерируем командуОР Rb+k-1, Rb+m-1, Rb+k-1 или ОР Rb+k-1, Rb+k-1, Rb+m-1в зависимости от того, является большой узел правымили левым.417.6 Генерация оптимального кода для выражений7.6.23.Алгоритм генерации кодадля размеченных деревьев выраженийДля листа, представляющего операнд х, при использовании базыb генерируем команду LD Rb, х.427.6 Генерация оптимального кода для выражений7.6.3Пример применения алгоритма генерации кодадля размеченных деревьев выраженийПрименим описанный алгоритм к дереву на рисунке.Поскольку метка корня равна 3, результат получится в регистреR3, а использоваться при вычислениях будут только регистрыR1, R2 и R3.1)Рассматривается корень t4.

У него два дочерних узла t1и t3 с одинаковыми метками, следовательно долженработать п.1 алгоритма.437.6 Генерация оптимального кода для выражений7.6.3Пример применения алгоритма генерации кодадля размеченных деревьев выражений2)3)Согласно п.1 (а) сначала нужно сгенерировать код дляправого поддерева (с корнем t3).У него правый узел большой, а левый – маленький,следовательно должен работать п.2 алгоритма.Согласно п.2 (а) сначала генерируется код для большогоподдерева (с корнем t2).447.6 Генерация оптимального кода для выражений7.6.3Пример применения алгоритма генерации кодадля размеченных деревьев выражений4)Рассматривается корень t2. У него два дочернихлистовых узла с одинаковыми метками, следовательнодолжен работать п.1 алгоритма.457.6 Генерация оптимального кода для выражений7.6.3Пример применения алгоритма генерации кодадля размеченных деревьев выражений5)Сначала согласно п.1 (а) нужно сгенерировать код дляправого листа, потом согласно п.1 (b) нужносгенерировать код для левого листа, потом согласноп.1 (c) нужно сгенерировать команду.

В результатеполучатся следующие три команды:LDLDADDR3, dR2, cR3, R2, R3467.6 Генерация оптимального кода для выражений7.6.3Пример применения алгоритма генерации кодадля размеченных деревьев выражений6)Далее генерируются команды для:левого поддерева дерева с корнем t3,для корня t3,для левого поддерева дерева с корнем t4и для всего дерева с корнем t4477.6 Генерация оптимального кода для выражений7.6.3Пример применения алгоритма генерации кодадля размеченных деревьев выраженийВ результате генерируется код :LDLDADDLDMULLDLDSUBADDR3,R2,R3,R2,R3,R2,R1,R2,R3,deR2,eR2,baR1,R2,R3R3R2R3487.6 Генерация оптимального кода для выражений7.6.4Вычисление выражений при недостаточном количестверегистровАлгоритм генерации кода для размеченного деревавыражения (с учетом конечного числа доступных регистров)Вход: (1)размеченное дерево, в котором каждый операндвстречается по одному разу (т.е.