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

При этом нет гарантии, чтоn-раскраска будет построенаПри исчерпании регистров применяются либо слив, либорасщепление ИЖ (узлов ГК).В обоих случаях исходный ГК преобразуется к новому ГК, которыйможет допускать n-раскраску.8.3 Глобальное распределение и назначение регистров8.3.10 Алгоритм раскраски графа конфликтов1 фаза. Установление порядка рассмотрения узловузлы по очереди удаляются из ГК и помещаются в стек.Узел ГК называется неограниченным, если его степень< n, и ограниченным, если его степень  n.Сначала в произвольном порядке удаляютсянеограниченные узлы вместе с дугами, соединяющими ихсо смежными узлами, при этом степень части смежныхузлов понижается, так что некоторые из ограниченныхузлов после удаления могут стать неограниченными.Если после удаления всех неограниченных узлов в ГКвсе еще остаются узлы, то все они ограничены. Длякаждого из ограниченных узлов вычисляется их степень(количество смежных узлов).Ограниченные узлы удаляются из графа и помещаются встек в порядке возрастания степени.В конце фазы граф конфликтов пуст, а все его узлы (ИЖ)находятся в стеке в некотором порядке.8.3 Глобальное распределение и назначение регистров8.3.10 Алгоритм раскраски графа конфликтов2 фаза.

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

После перестройки ГКделается переход на первую фазу.Ключевым моментом является порядок в котором узлы ГКпомещаются в стек.Наиболее распространенный эвристический критерий сливаузла – минимум отношенияцена _ сбросастепень _ узла8.3 Глобальное распределение и назначение регистров8.3.11 Структура распределителя регистровОпределениеИЖПостроениеГКВычислениестоимостисбросаРаскраскаГКПерестройкаГКРаскраска полученаНазначениерегистровНайти ИЖ всех переменных, построить ГК, вычислить стоимостьсброса для каждого ИЖ, выполнить раскраску ГК. После этоголибо каждый ИЖ получит цвет (положительный исход), либочасть ИЖ останутся неокрашенными (отрицательный исход).В случае положительного исхода каждому ИЖ присваиваетсяфизический регистр.В случае отрицательного исхода ГК перестраивается и сновавыполняется раскраска ГК.8.3 Глобальное распределение и назначение регистров8.3.12 Перестройка графа конфликтовПерестройка ГК достигается помимо слияния ИЖ (п.

8.3.9)с помощью сливания переменных (п. 8.3.13) ирасщепления ИЖ (п.8.3.14).8.3 Глобальное распределение и назначение регистров8.3.13 Сливание переменныхСливание временной переменной t состоит в следующем:в «автоматической» памяти процедуры выделить ячейкуta для хранения значений t (эту ячейку называют«дом» t);перед каждой командой, использующей t, вставитькоманду LD t, ta;после каждой команды, определяющей t, вставитькоманду ST ta, t;просматривают текст полученной процедуры с цельювыявить и удалить лишние команды LD и ST (иногда этоудается).8.3 Глобальное распределение и назначение регистров8.3.13 Сливание переменныхB1B2B1 ADD a, b, cADD a, b, cUMN d, aADD e, d, fB3MUL f, 2, eUMN d, aLD f, faADD e, d, fB2ADD b, d, eADD e, e, 1B3MUL f, 2, eST fa, fADD b, d, eADD e, e, 1B4ADD b, f, cabB4aХроматическое число 4fbХроматическое число 3fecdГКLD f, faADD b, f, cecd8.3 Глобальное распределение и назначение регистров8.3.14 Расщепление интервалов жизниADD a, m, 1ADD b, k, 4ADD r, b, mADD a, m, 1ST mem, aADD b, k, 4ADD r, b, mLDa, memADD a, m, 1ADD a, m, 1a и b в конфликтеКонфликт междуa и b устраненНа левом рисунке LRa и LRbполностью пересекаются.Расщепив LRa на два LR,удается устранить конфликт.При этом команды ST и LDприменяются только здесь, ане перед всеми a.8.3 Глобальное распределение и назначение регистров8.3.15 Примеры глобального распределения регистров1) Распределение виртуальных (символических) регистровB1 a  2bdegaB2 b  + b, 1d  * 2, db < 10B4B1 s1  2 3 c a + c, 1< dB3 d  + d, 1f  + a, bg  + e, gprint(b,d,e,g)s2s3s4s5s1B2 s2  + s2,1s3  * 2,s3s2 < 10B4 3 c s1 + s3,1< s3B3 s3  + s3,1s6  + s1,s2s5  + s4,s5print(s2,s3,s4,s5)8.3 Глобальное распределение и назначение регистров8.3.15 Примеры глобального распределения регистров2) Построение графа конфликтов( s1, …, s6 – виртуальные регистры, R1, …, R5 – физические регистры)s1R5s2R4s3R3s4R2s5R1s6 Все физические регистрысчитаются всегда живыми Пусть частота выполненияблоков B1, B3 и B4 равна 1, ачастота выполнения блока B2равна 7 Каждому символическомурегистру соответствует одининтервал жизни, поэтому,например, LRa и s1 –синонимы На символических регистрахs1, s2, s3, s4 хранятсязначения, поэтому результатывсех вычислений в блоках B2 иB3 будем помещать на R58.3 Глобальное распределение и назначение регистров8.3.15 Примеры глобального распределения регистровМатрица смежности графа конфликтов имеет видR2R3R4R5s1s2s3s4s5s6R1 R 2 R3 R 4 R5 s1 s 2 s3 s 4 s511111111110000100001 100001 1 100001 1 1 100000 1 1 1 100001 1 1 1 1 18.3 Глобальное распределение и назначение регистров8.3.15 Примеры глобального распределения регистровГраф конфликтов и его матрица смежности примут видs1R5s2R4s3R3R2s5R1s6R2R3R4R5s1s2s3s5s6R1 R 2 R3 R 4 R5 s1 s 2 s3 s511111111110000100001 100001 1 100001 1 1 100000 1 1 1 18.3 Глобальное распределение и назначение регистров8.3.15 Примеры глобального распределения регистровПоскольку каждый из узлов R1, R2, R3, R4 имеет меньше пяти смежных узлов,заталкиваем их в стек (порядок произвольный) и удаляем из графа конфликтов.Получается граф, изображенный на правом рисункеs1R4R5s2R3s1R5s2R2R4s3s3R1стекR3R2s5R1s6Граф конфликтов до исключенияузлов R1, R2, R3, R4s5s6Граф конфликтов после исключенияузлов R1, R2, R3, R48.3 Глобальное распределение и назначение регистров8.3.15 Примеры глобального распределения регистровТеперь узел R5 имеет меньше пяти смежных узлов; заталкиваем и его в стек и удаляем изграфа конфликтов.

Получается граф, изображенный на правом рисункеs1R5R5s2s1s2R4R3s3s3R2R1стекs5s6Граф конфликтовдо исключения узла R5s5s6Граф конфликтовпосле исключения узла R58.3 Глобальное распределение и назначение регистров8.3.15 Примеры глобального распределения регистровТеперь все оставшиеся узлы графа конфликтов имеют меньше пяти смежных узлов;заталкиваем их (в произвольном порядке) в стек и удаляем из графа конфликтов.s1s1s2s2s3s3s5s6R5R4R3s5s6R2R1стек8.3 Глобальное распределение и назначение регистров8.3.15 Примеры глобального распределения регистровВыталкиваем регистры из стека и присваиваем каждому свободный цвет (всего имеетсяпять цветов). R5 имеет 4 смежных узла: s1(1), s2(2), s3(3) и s6(5).

Следовательно, емуможно присвоить цвет 4 (только он свободен).РегистрЦветs1s11s2s22s33s54s65R5B2 R3 = R3 + 1R54R41R4R2 = 2 * R2R3 < 10R32R3R23R2R15s3s5s6R1стекB1 R4 = 2R3R2R5R4B4===<3cR2 + 1R2B3 R2 = R2 + 1R1 = R4 + R3R5 = R4 + R5print(R3,R2,R4,R5)8.3 Глобальное распределение и назначение регистровПрименим слияние интервалов к команде копирования s4 = s1 (в блоке B1). ПолучимОценим стоимости сброса для оставшихсясимволических регистров s1, s2, s3, s5 и s6B1 s1 = 2s2s3s5s1B2 s2 = s2 + 1s3 = 2 * s3s2 < 10===<3cs3 + 1s3B3 s3 = s3 + 1s6 = s1 + s2s5 = s1 + s5Символич.регистрСтоимость сбросаs12.0s21.0 + 21.0 + 2.0 + 2.0 = 26.0s36.0 + 20.0 + 4.0 + 2.0 = 32.0s52.0B1B2B3+ 4.0 + 2.0 = 8.0s6B4print(s2,s3,s1,s5)Spill_cost  DefWt 10def LRDepth( def )B4Стоимость сброса вычисляется по формуле UseWt 10useLRDepth( use) CopyWt 10Depth( copy)copyLRгде def, use и copy – отдельные команды определения, использования и копирования в LR,а DefWt, UseWt и CopyWt – стоимости соответствующих командПри вычислении стоимости сброса считается DefWt = UseWt = 2.0, CopyWt = 1.0Стоимость s6 = , так как регистр s6 – не является живым.