А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 138
Текст из файла (страница 138)
Хотя в общем случае задача определения, может ли граф быть раскрашен с использованием й цветов, является ХР-полной, обычно на практике для раскраски графов используется простая и быстрая эвристическая методика. Предположим, что узел п графа С имеет меньше, чем й соседей (узлов, соединенных дугами с п). Удалим и и его дуги из С, получив тем самым новый граф С~. к-раскраска С' может быть преобразована в й-раскраску С путем назначения узлу и цвета, не назначенного ни одному из его соседей. Многократно удаляя таким образом узлы с менее чем п соседями из графа взаимодействия регистров, мы получим либо пустой граф (в этом случае мы выполняем й-раскраску исходного графа, раскрашивая узлы в порядке, обратном порядку удаления), либо граф, в котором каждый узел имеет й или более смежных узлов.
В этом последнем случае )с-раскраска графа невозможна, и требуется сброс узла путем добавления кода для сохранения и перезагрузки регистра. Чаитин (Спайш) разработал ряд эвристических приемов для выбора сбрасываемого регистра. Общее правило состоит в том, чтобы избегать добавления кода для сброса во внутренний цикл. 8.8.5 Упражнения к разделу 8.8 Упражнение 8.8.1. Постройте граф взаимодействия регистров для программы, представленной на рис. 8.17.
Упражнение 8.8.2. Разработайте стратегию распределения регистров в предположении, что мы автоматически сохраняем все регистры в стеке перед каждым вызовом процедуры и восстанавливаем их после возвращения из нее. 8.9 Выбор команд путем переписывания дерева Выбор команд может представлять собой комбинаторную задачу большого размера, в особенности на машинах с богатым набором режимов адресации, таких как машины С!ЯС, или на машинах с командами специального назначения, например, для обработки сигналов. Даже если считать, что порядок вычислений задан и что регистры распределены с использованием отдельного механизма, выбор команд — задача выбора команд целевого языка для реализации операторов промежуточного представления — остается большой комбинаторной задачей.
Глава 8. Генерация кода 678 В этом разделе мы рассмотрим выбор команд как задачу изменения дерева. Представление целевых команд с использованием дерева эффективно использовалось в генераторах генераторов кода, которые автоматически создавали фазу выбора команд генератора кода на основании высокоуровневой спецификации целевой машины. Для некоторых машин лучший код можно получить при использовании ориентированных ациклических графов, а не деревьев, но работа с ориентированными ациклическими графами более сложна, чем работа с деревьями. 8.9.1 Схемы трансляции деревьев В этом разделе входом процесса генерации кода будет последовательность деревьев на семантическом уровне целевой машины.
Эти деревья представляют собой результат вставки адресов времени выполнения в промежуточное представление, как описано в разделе 8.3. Кроме того, листья деревьев содержат информацию о типах хранилищ для их меток. Пример 8.18. На рис. 8.19 показано дерево для инструкции присваивания а [1] =Ь+1, где массив а хранится в стеке времени выполнения, а переменная Ь вЂ” в глобальной ячейке памяти Мм Адреса времени выполнения локальных переменных а и 1 заданы как константные смещения С, и С, относительно ЯР— регистра, содержащего указатель на начало текущей записи активации.
Рис. 8.19, Дерево промежуточного кода для а[1]=Ь+1 Присваивание элементу а [1] является косвенным присваиванием, в котором г-значение ячейки памяти а [1] устанавливается равным г-значению выражения Ь+1. Адреса массива а и переменной 1 определяются путем сложения значений констант С, и С; соответственно с содержимым регистра ЯР. Для простоты мы считаем, что все значения представляют собой однобайтные символы (некото- 679 8.9. Выбор команд путем переписывания дерева рые наборы команд содержат специальные средства для умножений в процессе вычисления адресов на константы, такие как 2, 4 и 8).
В приведенном дереве оператор шп рассматривает свой аргумент как адрес памяти. В качестве левого дочернею узла оператора присваивания )пп дает адрес памяти, по которому будет сохранено г-значение правой части оператора присваивания. Если аргумент операторов + или шп' представляет собой ячейку памяти или регистр, то в качестве значения принимается содержимое этой ячейки памяти или регистра. Листья дерева представляют собой атрибуты (константа, регистр, ячейка памяти) с индексами, указывающими значения этих атрибутов. и Целевой код генерируется в процессе свертки входного дерева в единый узел путем последовательного применения правил преобразования дерева.
Каждое правило преобразования представляет собой инструкцию вида гер!асетеп! — !етр!аге (астап ) Здесь гер!асетепг — отдельный узел, гетр!а!е — дерево, а аейоп, как и в случае схемы синтаксически управляемой трансляции, является фрагментом кода. Множество правил преобразования дерева именуется схемой трансляции дерева (1гее-ггапз)айоп зсЬеше). Каждое правило преобразования дерева представляет собой трансляцию части дерева, определяемой шаблоном. Трансляция состоит из (возможно, пустой) последовательности машинных команд, которые генерируются действием, связанным с шаблоном.
Листья шаблона являются атрибутами с индексами, как и во входном дереве. Иногда к значениям индексов в шаблонах применяется ряд ограничений, определяемых в виде семантических предикатов, которым должен удовлетворять шаблон перед тем, как можно будет говорить о его соответствии, Например, предикат может требовать, чтобы значение константы находилось в определенном диапазоне. Схема трансляции дерева представляет собой удобный способ представления фазы выбора инструкций генератора кода. В качестве примера рассмотрим правило для инструкции сложения одного регистра с другим: ( хоп в,вь в~ ) Я, я, Это правило применяется следующим образом.
Если входное дерево содержит поддерево, соответствующее приведенному шаблону, т.е, поддерево, корень которого помечен оператором +, а его левый и правый потомки представляют собой величины, хранящиеся в регистрах г и 2, то мы можем заменить это поддерево одним узлом с меткой )2, и сгенерировать команду АП0 В(, Вг, В!'. Назовем 680 Глава 8. Генерация кода такую замену зомоьцелием (011п8) поддерева. Одно поддерево может соответствовать нескольким шаблонам; далее мы вкратце опишем механизм выбора правила в случае возникновения конфликтов.
Пример 8.19. На рис. 8.20 показаны правила преобразования для некоторых команд нашей целевой машины. Эти правила будут использоваться в последующих примерах данного раздела. Первые два правила соответствуют инструкциям загрузки, следующие два — инструкциям сохранения, а остальные — индексированным загрузкам и сложениям. Обратите внимание, что правило 8 требует, чтобы значение константы было равно 1. Это условие может определяться семантическим предикатом.
и Рис. 8.20. Правила преобразования дерева лля некоторых команд целевой машины 681 8.9. Выбор команд путем переписывания дерева 8.9.2 Генерация кода путем замощения входного дерева Схема трансляции дерева используется следующим образом. В данном входном дереве выполняется поиск поддеревьев, соответствующих имеющимся шаблонам правил преобразования. При соответствии шаблону поддерево заменяется узлом, определяемым правилом преобразования, и выполняются связанные с правилом действия.
Если действие содержит последовательность машинных команд, они выводятся в выходной поток. Этот процесс повторяется до тех пор, пока в дереве имеются поддеревья, соответствующие шаблонам, и исходное дерево не свернуто в единственный узел. Последовательность машинных команд, генерируемая в процессе свертки входного дерева в один узел, образует выход схемы трансляции для данного входного дерева. Процесс определения генератора кода аналогичен использованию схемы синтаксически управляемой трансляции для определения транслятора.
Мы создаем схему трансляции дерева для описания набора команд целевой машины. На практике мы должны найти такую схему, которая приведет к генерации последовательности команд с минимальной стоимостью для каждого входного дерева. Существуют специальные инструментальные средства, облегчающие автоматическое построение генератора кода по схеме трансляции дерева. Пример 8.20. Воспользуемся схемой трансляции дерева на рис.
8.20 для генерации кода, соответствующего дереву, приведенному на рис. 8.19. Предположим, что правило 1 применяется к загрузке константы С, в регистр ВО: ( ьоно,()а) () я„— с, При этом метка крайнего слева листа С, заменяется меткой г(о и генерируется команда ЬР ВО, $а.
Теперь правило 7 ( Ало ко, ко, зг ) 7) ко <- яа я5Р соответствует крайнему слева поддереву с меткой корня +. Используя это правило, мы заменим указанное поддерево одним узлом с меткой Ло и сгенерируем команду АРР КО, ВО, ЯР. В результате дерево будет выглядеть следующим образом; Глава 8. Генерация кода 682 Теперь можно применить правило 5 для свертки поддерева / ' в единственный узел с меткой Вы Однако можно воспользоваться правилом 6 для свертки большего дерева в единственный узел с меткой Ло и генерации команды А)ЗП йО, ВО, з(ЯР). Считая, что более эффективным является использование одной команды для вычисления большего дерева, мы выбираем последний вариант и получаем после свертки дерево ЯО М~ С, В правом поддереве к листу Мь мы применим правило 2, которое сгенернрует команду загрузки Ь в регистр, для определенности — регистр В1.
В результате поддерево 683 8.9. Выбор команд путем переписывания дерева соответствует шаблону правила 8 и при свертке дает команду 1ЫС К1. Теперь входное дерево свернуто в дерево Оно соответствует поддереву из правила 4, применение которого дает в результате единственный узел и генерирует команду ЯТ *КО, К1. Итак, в процессе свертки исходного дерева в единственный узел мы получили следующий код: Юа КО, ЯР КО, 1(ЯР) Ь 1Р КО, АРР КО, АРР КО, 1Р К1, 1ЫС К1 ЯТ *КО, К1 Для реализации процесса свертки дерева из примера 8.18 нам надо решить пару вопросов, связанных с поиском соответствия деревьев шаблону. ° Каким образом выполняется поиск соответствия? Эффективность процесса генерации кода в процессе компиляции зависит от того, насколько эффективен применяющийся алгоритм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
