Лекция 08. Распределение и назначение регистров (1157466), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Это задача анализа потока данных. Методомитераций решается система уравненийLiveIn[ B]  useB  ( LiveOut[ B]  VarKill B )(1)LiveOut[ B] (2) LiveIn[s]sSucc ( B )где LiveOut(B) – множество переменных, живых на выходе из B,LiveIn(B) – множество переменных, живых на входе в B,use(B) – множество переменных блока B, которые используютсяв B до их переопределения в B,VarKillB – множество переменных блока B, которыепереопределяются в B (оно обозначалось как defB).Решив методом итераций систему (1), (2),получим LiveOut(B) для всех B.8.3 Глобальное распределение и назначение регистров8.3.2 Построение интервалов жизниИсследование отношений между различными определениямии использованиями. Нужно построить множества всехопределений, достигающих одного и того же использования(UD-цепочки), и всех использований, которые достигаются одними тем же определением (DU-цепочки).Такое построение удобно проводить в SSA-форме, так как в нейкаждое имя определяется только один раз,каждое использование ссылается на единственное имя,а объединение имен обеспечивается с помощью -функций.Для программы в SSA-форме требуемая группировка имендостигается за один просмотр.Алгоритм объединения имен анализирует каждую -функцию истроит объединение множеств, связанных с каждым еепараметром, и множества, связанного с определяемой еюпеременной.

Это объединение и представляет интервал жизни.После обработки всех -функций строится отображениеSSA-имен на имена интервалов жизни.8.3 Глобальное распределение и назначение регистров8.3.3 Построение интервалов жизни. ПримерB0B0…a0  …B1B2b0  ……  b0d0  …B3…LRa  …B1c0  ……d1  c0d2  (d0, d1)…  a0…  d2Фрагмент кодав SSA-представленииLRa = {a0}LRb = {b0}LRc = {c0}LRd == {d0,d1,d2}B2LRb  ……  LRbLRd  …LRc  ……LRd  LRcB3…  LRa…  LRdТот же фрагмент, переписанный втерминах интервалов жизни8.3 Глобальное распределение и назначение регистров8.3.4 Оценка стоимости сбросаСтоимость сброса складывается из следующих трех компонент:стоимость вычисления адресов при сбросестоимость операций доступа к памятиоценка частоты выполненияДля хранения сброшенных значений во фрейме процедурывыделяется специальная область.Это позволяет свести к минимуму стоимость вычисленияадресов при сбросе, исключив использование косвеннойадресации и дополнительных регистров для вычисленияадреса сбрасываемого значения.Интервал жизни, который содержит только команды загрузкирегистра и его сохранения может иметьотрицательную стоимость сбросав случае, когда обе команды обращаются к одному и тому жеадресу памяти.

Такие ситуации могут возникнуть вследствиеисключения избыточных вычислений.8.3 Глобальное распределение и назначение регистров8.3.4 Оценка стоимости сбросаЧтобы учитывать частоту выполнения базовых блоков в графепотока управления, каждый базовый блок снабжаетсяаннотацией, содержащей оценку стоимости его выполнения(профилирование).Для получения грубой оценки стоимости частоты выполненияиспользуется простая эвристика:делается допущение, что каждый цикл выполняется 10 раз; тогдастоимость каждой загрузки внутри одного цикла оценивается как10, внутри гнезда из двух циклов – как 100 и т.д.; стоимостькаждой ветви непредсказуемого if-then-else оцениваетсякак 0.5.На практике из этой эвристики, в частности, следует, что сбросвыгоднее выполнять в более внешнем цикле.Аннотации могу вычисляться заранее (и тогда потребуетсядополнительный просмотр программы), либо во время первогообращения8.3 Глобальное распределение и назначение регистров8.3.5 Конфликтные ситуации и граф конфликтовПри распределении регистров моделируется состязание заместо на регистрах целевой машины.Рассмотрим два различных интервала жизни LRi и LRj.

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

Этот графне является направленным, так как отношение нахождения вконфликте симметрично.Таким образом, если два узла ГК являются смежными(соединены дугой), то им должны соответствовать различныерегистры.8.3 Глобальное распределение и назначение регистров8.3.6 Раскраска графаРаскраска произвольного графа G состоит в присвоении каждомуузлу G определенного цвета таким образом, чтобы любым двумсмежным узлам G не были сопоставлены одинаковые цвета.Раскраска, использующая n цветов называется n-раскраской, анаименьшее из таких n называется хроматическим числомграфа.На рисунке внизу хроматическое число левого графа равно 2,а правого графа – 3.Проблема нахождения хроматического числа графа и проблемавыяснения, допускает ли граф n-раскраску NP-полны.ABCEADBCED8.3 Глобальное распределение и назначение регистров8.3.7 Раскраска графа конфликтовB0Если у целевого компьютера nрегистров, то проблема ихраспределения для программысводится к проблеме построенияn-раскраски ГКВ частности, для данногопримера ГК допускает2-раскраску, следовательно,достаточно 2 регистров…LRa  …B1B2LRb  ……  LRbLRd  …LRc  ……LRd  LRcLRaLRdLRbLRcB3…  LRa…  LRdФрагмент кода с именамиинтервалов жизниГраф конфликтов8.3 Глобальное распределение и назначение регистров8.3.7 Раскраска графа конфликтовЕсли оптимизирующая фаза компиляторапереставила две последние команды блока B1Тогда LRb будет живым при определении LRd,B0и значит в ГК необходимо добавить дугу…LRa  …(LRb, LRd) в результате чего ГК уже не будетдопускать 2-раскраску, так как (LRa,LRb и LRdдолжны быть разного цвета)B1B2Теперь ураспределителяLRb  …LRc  …регистров двеLRd  ……возможности:…  LRbLRd  LRc1: ИспользоватьLRaLRdтретий регистр2: ПередB3определениемрегистра для LRd…  LRaLRbLRcсбросить LRa или…  LRdФрагмент кода с именами интервалов жизниГраф конфликтовLRb8.3 Глобальное распределение и назначение регистров8.3.8 Построение графа конфликтовПосле построения глобальных интервалов жизни и множествLiveOut для каждого базового блока можно за один просмотрпрограммы от Exit к Entry построить ГК.Внутри каждого базового блока алгоритм поддерживаетмножество LiveNow переменных, живых в текущей точке блока.При входе в блок B полагают LiveNow = LiveOut(B).Затем просматривают каждую команду блока (op LRa, LRb, LRc)и узел ГК, соответствующий переменной LRa, определяемой вэтой команде, соединяют дугами со всеми узлами,соответствующими переменным из LiveNow (это как разпеременные, живые во время определения другой переменной).Для повышения эффективности ГК задается левой (нижней)половиной своей матрицы смежности.Операции копирования LRi  LRj не порождают конкуренциимежду LRi и LRj, так как эти значения могут занимать один и тотже регистр.8.3 Глобальное распределение и назначение регистров8.3.8 Построение графа конфликтовБолее точно алгоритм можно выразить следующим образом:for each LRi docreate a node ni  N;for each basic block b do{LiveNow = LiveOut(b)for In, In-1, …, I1 in b do{||Ik имеет вид opk LRa, LRb, LRcfor each LRi  LiveNow{add (LRa, LRi) to Eremove LRa from LiveNowadd LRb to LiveNowadd LRc to LiveNow}}}8.3 Глобальное распределение и назначение регистров8.3.9 Слияние интервалов жизниРассмотрим команду копирования LRi = LRj.

Если ИЖ LRi и LRjне находятся в конфликте (не являются смежными узлами ГК),то команду можно исключить и все ссылки на LRj заменитьссылками на LRi. В результате ИЖ LRi и LRj как бы сольются.Слияние ИЖ приносит следующие выгоды:Исключается команда копирования (код становитсяменьше и тем самым потенциально быстрее)Снижается степень каждого узла (ИЖ), который был вконфликте либо с LRi, либо с LRj.Множество ИЖ сокращается (в литературе приводитсяпример, когда в результате слияния ИЖ удалосьисключить свыше 30% всех ИЖ).8.3 Глобальное распределение и назначение регистров8.3.9 Слияние интервалов жизниПример.

Рассмотрим фрагмент программы:aADDLRa, LRt, LRu.....................bLDLRb, LRacLDLRc, LRa.....................ADDLRx, LRb, LRwADDLRz, LRc, LRyОтрезки справа от кода отмечают ИЖ LRa LRb LRc(красным показано определение переменной, зеленым – ее последнееиспользование).Несмотря на то, что ИЖ LRa пересекается и с LRb, и с LRc, он ненаходится в конфликте ни с тем, ни с другим, так как источник и приёмниксоответствующих команд копирования не находятся в конфликте.LRb и LRc находятся в конфликте, так как LRb жив при определении LRcИЖ из обеих операций копирования являются кандидатами на слияние.8.3 Глобальное распределение и назначение регистров8.3.9 Слияние интервалов жизниПосле слияния LRa и LRb:abADDLRab, LRt, LRu.....................LDLRc, LRabc.....................ADDLRx, LRab, LRwADDLRz, LRc, LRyПосле слияния ИЖ LRa и LRb получаем новый ИЖ LRab.Теперь ИЖ LRc получается из LRab командой копирования, иследовательно LRc и LRab не находятся в конфликте, так чтослияние LRa и LRb в LRab понизило степень LRc.Слияние ИЖ может или уменьшить степени смежных узлов (ИЖ),или оставить их без изменения.Команда копирования LD LRc,LRab позволяет продолжитьпроцесс слияния ИЖ, заменив LRab на LRabc.8.3 Глобальное распределение и назначение регистров8.3.10 Эвристики раскраски графа конфликтовПосле того как ГК построен, необходимо решить две задачи:Для построенного ГК необходимо найти n-раскраску(n – число регистров целевой машины)Необходимо разработать алгоритм обработки ситуации,когда при необходимости раскраски очередного интервалажизни (узла ГК) выясняется, что все n цветов исчерпаныПоскольку проблема n-раскраски графа NP-полна, применяютсябыстрые эвристические алгоритмы.

Характеристики

Список файлов лекций