Теормин (2015) (Теормин), страница 3

Каждоеправило преобразования дерева представляет собой инструкцию видаreplacement ← template {action}, где replacement – отдельный узел, template –шаблон (поддерево), action – действие (фрагмент генерируемого кода,соответствующий шаблону). Множество правил преобразования дереваименуется схемой трансляции дерева. {ADD Ri, Ri, Rj}Ri ← +Если входное дерево содержит поддерево, соответствующееданному шаблону, то это поддерево можно заменить одним узлом RRjiс меткой Ri и сгенерировать команду ADD Ri, Ri, Rj.54. Гнездо циклов *** - композиция нескольких циклов (один в другом).19Распределение регистровотображает неограниченное множество имен (псевдорегистров)на конечное множество физических регистров целевой машины,Это NP-полная задача55. Локальное распределение регистров (1)Дескриптор DR[r] регистра r указывает, значение какойпеременной содержится на регистре r (на каждом регистре могутхраниться значения одного или нескольких имен)Дескриптор DA[a] переменной a указывает адрес текущегозначения a.

Это может быть регистр, адрес памяти, указательстекаПусть определена функция getReg (I), имеющая доступ ко всемдескрипторам регистров и адресов, а также к другим атрибутамобъектов, хранящимся в таблице символов,которая назначает регистры для операндов и результатакоманды I.Функция getReg (I) позволяет назначать регистры во времявыбора команд2055. Локальное распределение регистров (2)Реализация функции getRegВыбор регистра Ry для операнда yЕсли DA[y] не содержит ссылок на регистры и неимеется ни одного регистра R, для которого DR[R] несодержит ссылок ни на одну переменную, то R можноиспользовать в качестве Rу , если для каждой переменнойv, ссылка на которую содержится DR[R], выполняется одноиз следующих условий: DA[v] содержит ссылку не только на R, но и на адрес v, v представляет собой переменную х, вычисляемуюкомандой I, и х не является одновременно одним изоперандов команды I, переменная v после команды I больше не используется.Если ни одна из перечисленных выше ситуаций не имеетместа, то прежде чем использовать R в качестве Rу,необходимо выполнить сброс регистра, т.е.

команду 21ST v, R55. Локальное распределение регистров (3)Реализация функции getRegВыбор регистра Rx для результата xЕсли DR[R] ссылается только на х, то полагаем Rх = RЭто можно делать даже тогда, когда х является одним изу или z, так как в одной машинной команде допускаетсясовпадение двух регистров.Если y не используется после команды I и если DR[Ry]ссылается только на y, то Ry может использоватьсяв роли Rx.Если z не используется после команды I и если DR[Rz]ссылается только на z, то Rz может использоватьсяв роли Rx.Генерация команд для инструкции Iх ← уСначала выбирается Ry, как и для операнда инструкциих ← op, y, z, после чего полагается Rx = Ry.2256. Глобальное распределение регистровПри распределении регистров моделируется состязание заместо на регистрах целевой машины.Рассмотрим два различных интервала жизни LRi и LRj.

Если впрограмме существуют команды, во время которых и LRi, и LRjактуальны, то они не могут занимать один и тот же регистр.В таком случае говорят, что LRi и LRj находятся в конфликте.Определение. Интервалы жизни LRi и LRj находятся вконфликте если один из них актуален при определении другогои они имеют различные значения.Граф, узлы которого соответствуют отдельным интерваламжизни, а дуги соединяют интервалы жизни, находящиеся вконфликте, называется графом конфликтов (ГК). Этот графне является направленным, так как отношение нахождения вконфликте симметрично.Таким образом, если два узла ГК являются смежными(соединены дугой), то им должны соответствовать различныерегистры.2357.

Планирование кодаЦель планирования кода – выбрать такую последовательность команд,которая, не меняя семантики программы, обеспечит оптимальное использованиеособенностей архитектуры целевого процессора Прежде всего, это необходимость обеспечить правильно использованиевозможностей параллельного выполнения команд, реализованных в аппаратуреданного целевого процессораТребование сохранения семантики программы проще всеговыразить в форме ограничений, которым должна удовлетворятьцелевая программа. Эти ограничения должны гарантировать, чтооптимизированная программа будет давать такие же результаты,и исходная.чтоНа планирование кода накладывается следующие три типаограничений:Ограничения управления. Все операции, выполняемыев исходной программе, должны выполняться и воптимизированной программе.Ограничения данных.

Операции в оптимизированнойпрограмме должны выдать те же результаты, что исоответствующие операции в исходной программеОграничения ресурсов. Планирование кода не должнотребовать чрезмерного количества ресурсов машины.2459-60. Зависимости по управлениюКоманда s1 зависит по управлению от команды s2, есливыполнение команды s2 определяет, будет ли выполнятьсякоманда s1.Простые примерыв конструкции if(с) s1; else s2;s1 и s2 зависят по управлению от св конструкции while (с) s;s зависит по управлению от c2562. Зависимости по даннымОпределение. Две команды называются зависимыми поданным, если изменение порядка их выполнения может привестик изменению результата вычислений, выполняемых программой.Виды зависимостей по данным:Истинная зависимость: чтение после записи.Если команда C1 записывает значение в некоторую ячейкупамяти (или на регистр), а команда C2 считывает этозначение, то команды C1 и C2 зависимы.Антизависимость: запись после чтения.Если команда C1 считывает значение из некоторой ячейкипамяти, а команда C2 записывает в эту ячейку новоезначение, то команды C1 и C2 зависимы.Зависимость по выходу: запись после записи.Если команды C1 и C2 записывают значения в одну и туже ячейку памяти, то команды C1 и C2 зависимы.2663.

Переименование значений, чтобы избежать антизависимостей.Значения переименовываются таким образом, чтобы каждое значение имелоуникальное имя. Это нужно для того, чтобы найти и те расписания, которые былибы исключены из-за антизависимостей.64. Требование консервативности анализаКонсервативность. Компилятор обязан считать, что двекоманды могут обращаться к одним и тем же ячейкам, еслион не может доказать обратное.Пример: Рассмотрим код1. a ← 12.

*p ← 23. b ← aСразу можно обнаружить истинную зависимость междукомандами 1 и 3.Больше зависимостей как будто нет, но это только в том случае,если компилятор может доказать, что указатель p не можетуказывать на a.В противном случае, компилятор обязан считать, что указатель pможет указывать на a, и тогда возникают еще две зависимости:истинная зависимость между командами 2 и 327зависимость по записи между командами 1 и 2.65.

В чем состоит анализ потока данных ***При анализе потока данных рассматриваются множества переменных дляописания состояния и такие операции как объединение и пересечение множеств.Структурой потока данных называется четверка <D, F, L, ∧> , гдеD – направление анализа (Forward или Backward), F – семейство передаточныхфункций, L – поток данных, ∧ - операция сбора.На выходе получаем значения из L для In[B] и Out[В] для каждого блока Вв графе потока.66-69. Дуги ГПУ:Дуги ГПУ, являющиеся дугами и его остовного дерева, называются остовными.Дуги ГПУ, не являющиеся дугами его остовного дерева, но имеющие такое женаправление, что и остовные, называются прямыми.Дуги ГПУ, направленные противоположно остовным, называются обратнонаправленными. Обратно направленная дуга ГПУ 〈Bi, Bk〉 называется обратной,если Bk = Dom(Bi).Остальные дуги ГПУ называются поперечными.

Поперечные дуги соединяютразличные поддеревья остовного дерева и в программах нормальныхпрограммистов не встречаются.70. Алгоритм Mark & Sweep.Алгоритм Mark & Sweep (двухпроходный), применяющийся дляосвобождения динамической памяти в сборщиках мусора, можетиспользоваться и для исключения бесполезного кода.Инструкция называется полезной, если она:вычисляет возвращаемое значение процедурыявляется обращением к функции ввода-выводавычисляет значение глобальной переменной, доступнойиз других процедурее результат используется в других полезных инструкциях.Алгоритм состоит из двух проходов:на первом проходе (Mark) выявляются и помечаютсяполезные инструкции.на втором проходе (Sweep) непомеченные инструкцииудаляются.29.