Лекция 10. Заключение (Лекции (2015)), страница 3

Каждая команда копирования описывается четверкойx, y, b, p, где x и y представляют инструкцию копированияx  y, находящуюся в строке p базового блока b.Множество всех таких четверок обозначим через U. Множество Uсодержит все инструкции копирования анализируемой процедуры.3910.1 Что было рассказано10.1.20 Распространение копийСистема уравнений составляется по аналогии с системойуравнений для достигающих определений:сначала из множества инструкций копированияудаляются инструкции «убитые» в блоке b, потом в негодобавляются инструкции копирования блока b.Второе уравнение содержит операцию пересечения, таккак по всем путям должны приходить одинаковые копии.OutCP (b)  copy(b)  ( InCP (b)  kill(b))InCP (b)   OutCP ( p)pPred(b)4010.1 Что было рассказано10.1.21 Оптимизация цикловПостроение натурального цикла по обратной дугеВход:ГПУ G = N, Е с входным узлом Entry.Обратная дуга e = n, d  EВыход:подграф C G, являющийся натуральным циклом.Метод:(1)начальное значение С – множество {n, d}.(2)узел d помечается как «посещенный».(3)начиная с узла n выполняется поиск в глубину(4)на обратном графе потока (направления дугзаменены на противоположные).все узлы, посещенные на шаге (3), добавляютсяв C.4110.1 Что было рассказано10.1.21 Оптимизация цикловПеремещение кода, инвариантного относительно циклаИнструкция инвариантна относительно цикла, если онаудовлетворяет одному из следующих условий: ее операнды – константы все определения операндов, достигающие инструкции находятсявне цикла внутри цикла имеется в точности одно определение операнда, нооно само инвариантно относительно цикла.Алгоритм:1.

Перед заголовком цикла вставить пустой базовый блок(будущий предзаголовок).Для всех инструкций в теле цикла:2. Отметить как инвариантные все операнды-константы3. Отметить как инвариантные все операнды, у которых всеопределения, достигающие инструкции, находятся вне цикла4. Отметить как инвариантные все инструкции, все операндыкоторых отмечены5. Повторять шаги 2 – 4, пока инвариантные инструкции неперестанут выделяться426. Переместить все выделенные инструкции в предзаголовок.10.1 Что было рассказано10.1.21 Исключение бесполезного кодаПрограмма может содержать бесполезный код – инструкции,не влияющие на результат вычислений.

Как правило, бесполезныйкод появляется в программе в результате работы некоторыхалгоритмов анализа и оптимизации, реализованных вкомпиляторе.Существует несколько разновидностей бесполезного кода:Мертвый код – инструкции, результат которыхне используется в дальнейших вычислениях.Недостижимый код – инструкции, которыене содержатся ни в одном реальном пути выполнения.Избыточный код – инструкции, повторно вычисляющиеуже вычисленные значения (например, доступныевыражения или инвариантные вычисления в циклах).Требуется обнаружить и удалить бесполезный (в частности,недостижимый и мертвый) код4310.1 Что было рассказано10.1.21 Исключение бесполезного кодаАлгоритм Mark & Sweep.Алгоритм Mark & Sweep (двухпроходный), применяющийся дляосвобождения динамической памяти в сборщиках мусора, можетиспользоваться и для исключения бесполезного кода.Инструкция называется полезной, если она:вычисляет возвращаемое значение процедурыявляется обращением к функции ввода-выводавычисляет значение глобальной переменной, доступнойиз других процедурее результат используется в других полезных инструкциях.Алгоритм состоит из двух проходов:на первом проходе (Mark) выявляются и помечаютсяполезные инструкции.на втором проходе (Sweep) непомеченные инструкцииудаляются.4410.1 Что было рассказано10.1.22 Генерация кодаОсновные фазы генерации кодаВыбор командРаспределение регистровВыбор оптимального порядка команд (планирование кода)Выбор командКаждая команда целевого языка имеет стоимость.Стоимость команды равна единице плюс сумме стоимостей,связанных с режимами адресации операндов:Стоимость операнда на регистре равна 0Стоимость операнда из ячейки памяти равна 1Стоимость операнда-константы равна 1Стоимость каждого разыменования равна 1Стоимость программы (на целевом языке) равна сумместоимостей ее команд.

Чем меньше стоимость программы, тембыстрее она выполняетсяАлгоритм генерации кода должен минимизировать стоимостьпрограммы.4510.1 Что было рассказано10.1.22 Генерация кодаСхема трансляции дереваСхема трансляции задается набором правил сверткиКаждое правило свертки содержит:метку узла, на который заменяется поддерево при сверткеподдерево, соответствующее рассматриваемому шаблонукоманды, которые помещаются в объектную программупри сверткеПример правила: правило для команды сложения одного регистра сдругим имеет вид:{ADD Ri, Ri, Rj}Ri  +RjRiесли входное дерево содержит поддерево, соответствующее данномушаблону, то это поддерево можно заменить одним узлом с меткой Ri исгенерировать команду ADD Ri, Ri, Rj.замещением поддерева.В случае использования обобщенных шаблонов для выбораТакая замена называетсякоманд в частных случаях могут использоваться семантическиепроверки4610.1 Что было рассказано10.1.23 Распределение и назначение регистровРаспределение регистровотображает неограниченное множество имен (псевдорегистров)на конечное множество физических регистров целевой машины,Это NP-полная задачаНазначение регистровотображает множество распределенных имен регистров нафизические регистры целевого процессора.

Для решения этойзадачи известно несколько алгоритмов полиномиальнойсложности.Во время назначения регистров предполагается, чтораспределение регистров уже было выполнено, так что пригенерации каждой команды требуется не более n регистров(n – число физических регистров).4710.1 Что было рассказано10.1.23 Распределение и назначение регистровЛокальное распределение регистровДескриптор DR[r] регистра r указывает, значение какойпеременной содержится на регистре r (на каждом регистре могутхраниться значения одного или нескольких имен)Дескриптор DA[a] переменной a указывает адрес текущегозначения a.

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

команду 49ST v, R10.1 Что было рассказано10.1.23 Распределение и назначение регистровРеализация функции 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.5010.1 Что было рассказано10.1.23 Распределение и назначение регистровГлобальное распределение регистровПри распределении регистров моделируется состязание заместо на регистрах целевой машины.Рассмотрим два различных интервала жизни LRi и LRj.

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

Этот графне является направленным, так как отношение нахождения вконфликте симметрично.Таким образом, если два узла ГК являются смежными(соединены дугой), то им должны соответствовать различные51регистры.10.1 Что было рассказано10.1.23 Распределение и назначение регистровАлгоритм раскраски графа конфликтов1 фаза. Установление порядка рассмотрения узловузлы по очереди удаляются из ГК и помещаются в стек.Узел ГК называется неограниченным, если его степень< n, и ограниченным, если его степень  n.Сначала в произвольном порядке удаляютсянеограниченные узлы вместе с дугами, соединяющими ихсо смежными узлами, при этом степень части смежныхузлов понижается, так что некоторые из ограниченныхузлов после удаления могут стать неограниченными.Если после удаления всех неограниченных узлов в ГКвсе еще остаются узлы, то все они ограничены.

Длякаждого из ограниченных узлов вычисляется их степень(количество смежных узлов).Ограниченные узлы удаляются из графа и помещаются встек в порядке возрастания степени.В конце фазы граф конфликтов пуст, а все его узлы (ИЖ)находятся в стеке в некотором порядке.5210.1 Что было рассказано10.1.23 Распределение и назначение регистровАлгоритм раскраски графа конфликтов2 фаза. Раскраска узловраспределитель восстанавливает ГК, выбирая из стека очереднойузел l и раскрашивая его в цвет, отличный от цвета смежныхузлов. Если оказывается, что все цвета использованы, узел lостается нераскрашенным.В конце фазы стек пуст, а ГК восстановлен и часть его узловраскрашена.3 фаза. Проверка на окончание процесса раскраскиЕсли нераскрашенных узлов не осталось, алгоритм завершается.Если часть узлов ГК осталась нераскрашенной, то для каждоготакого узла либо генерируются команды сброса (слив), либоинтервал жизни, соответствующий узлу расщепляется (на дваили более подинтервалов), после чего ГК перестраивается сучетом слива и/или разделенных узлов.

После перестройки ГКделается переход на первую фазу.Ключевым моментом является порядок в котором узлы ГК53помещаются в стек.10.1 Что было рассказано10.1.23 Распределение и назначение регистровАлгоритм раскраски графа конфликтовОпределениеИЖПостроениеГКВычислениестоимостисбросаРаскраскаГКПерестройкаГКРаскраска полученаНазначениерегистровНайти ИЖ всех переменных, построить ГК, вычислить стоимостьсброса для каждого ИЖ, выполнить раскраску ГК. После этоголибо каждый ИЖ получит цвет (положительный исход), либочасть ИЖ останутся неокрашенными (отрицательный исход).В случае положительного исхода каждому ИЖ присваиваетсяфизический регистр.В случае отрицательного исхода ГК перестраивается и сновавыполняется раскраска ГК.5410.1 Что было рассказано10.1.24 Планирование кодаЦель планирования кода – выбрать такую последовательностькоманд, которая, не меняя семантики программы, обеспечитоптимальное использование особенностей архитектурыцелевого процессораПрежде всего, это необходимость обеспечить правильноеиспользование возможностей параллельного выполнениякоманд, реализованных в аппаратуре данного целевогопроцессора5510.1 Что было рассказано10.1.24 Планирование кодаТребование сохранения семантики программы проще всеговыразить в форме ограничений, которым должна удовлетворятьцелевая программа.