Тема 13 2018Распределение_и_назначение. 13. Распределение и назначение регистров 13. 1
 Скачать 0.73 Mb.
|
|
LR i LR j не порождают конкуренции между LR i и LR j , так как эти значения могут занимать один и тот же регистр. 13.3 Глобальное распределение и назначение регистров 13.3.8 Построение графа конфликтов Более точно алгоритм можно выразить следующим образом: for each LR i do create a node n i N; for each basic block b do{ LiveNow = LiveOut(b) for I n , I n-1 , …, I 1 in b do{ ||I k имеет вид op k LR a , LR b , LR c for each LR i LiveNow{ add (LR a , LR i ) to E remove LR a from LiveNow add LR b to LiveNow add LR c to LiveNow } } } 13.3 Глобальное распределение и назначение регистров 13.3.9 Слияние интервалов жизни Рассмотрим команду копирования LR i = LR j Если ИЖ LR i и LR j не находятся в конфликте (не являются смежными узлами ГК), то команду можно исключить и все ссылки на LR j заменить ссылками на LR i . В результате ИЖ LR i и LR j как бы сольются Слияние ИЖ приносит следующие выгоды: Исключается команда копирования(код становится меньше и тем самым потенциально быстрее) Снижается степень каждого узла (ИЖ), который был в конфликте либо с LR i , либо с LR j Множество ИЖ сокращается (в литературе приводится пример, когда в результате слияния ИЖ удалось исключить свыше 30% всех ИЖ). 13.3 Глобальное распределение и назначение регистров 13.3.9 Слияние интервалов жизни Пример. Рассмотрим фрагмент программы: ADD LR a , LR t , LR u ..................... LD LR b , LR a LD LR c , LR a ..................... ADD LR x , LR b , LR w ADD LR z , LR c , LR y Отрезки справа от кода отмечают ИЖ LR a LR b LR c ( красным показано определение переменной, зеленым – ее последнее использование ). Несмотря на то, что ИЖ LR a пересекается и с LR b , и с LR c , он не находится в конфликте ни с тем, ни с другим, так как источник и приёмник соответствующих команд копирования не находятся в конфликте. LR b и LR c находятся в конфликте, так как LR b жив при определении LR c ИЖ из обеих операций копирования являются кандидатами на слияние. a b c 13.3 Глобальное распределение и назначение регистров 13.3.9 Слияние интервалов жизни После слияния LR a и LR b : ADD LR ab , LR t , LR u ..................... LD LR c , LR ab ..................... ADD LR x , LR ab , LR w ADD LR z , LR c , LR y После слияния ИЖ LR a и LR b получаем новый ИЖ LR ab Теперь ИЖ LR c получается из LR ab командой копирования, и следовательно LR c и LR ab не находятся в конфликте, так что слияние LR a и LR b в LR ab понизило степень LR c Слияние ИЖ может или уменьшить степени смежных узлов (ИЖ), или оставить их без изменения. Команда копирования LD LR c ,LR ab позволяет продолжить процесс слияния ИЖ, заменив LR ab на LR abc ab c 13.3 Глобальное распределение и назначение регистров 13.3.10 Эвристики раскраски графа конфликтов После того как ГК построен, необходимо решить две задачи : Для построенного ГК необходимо найти n - раскраску ( n – число регистров целевой машины) Необходимо разработать алгоритм обработки ситуации, когда при необходимости раскраски очередного интервала жизни (узла ГК) выясняется, что все n цветов исчерпаны Поскольку проблема n - раскраски графа NP -полна, применяются быстрые эвристические алгоритмы. При этом нет гарантии, что n - раскраска будет построена При исчерпании регистров применяются либо слив , либо расщепление ИЖ (узлов ГК). В обоих случаях исходный ГК преобразуется к новому ГК, который может допускать n - раскраску. 13.3 Глобальное распределение и назначение регистров 13.3.10 Алгоритм раскраски графа конфликтов 1 фаза. Установление порядка рассмотрения узлов узлы по очереди удаляются из ГК и помещаются в стек. Узел ГК называется неограниченным, если его степень < n , и ограниченным, если его степень n. Сначала в произвольном порядке удаляются неограниченные узлы вместе с дугами, соединяющими их со смежными узлами, при этом степень части смежных узлов понижается, так что некоторые из ограниченных узлов после удаления могут стать неограниченными. Если после удаления всех неограниченных узлов в ГК все еще остаются узлы, то все они ограничены. Для каждого из ограниченных узлов вычисляется их степень ( количество смежных узлов). Ограниченные узлы удаляются из графа и помещаются в стек в порядке возрастания степени. В конце фазы граф конфликтов пуст, а все его узлы (ИЖ) находятся в стеке в некотором порядке. 13.3 Глобальное распределение и назначение регистров 13.3.10 Алгоритм раскраски графа конфликтов 2 фаза. Раскраска узлов распределитель восстанавливает ГК, выбирая из стека очередной узел l и раскрашивая его в цвет, отличный от цвета смежных узлов. Если оказывается, что все цвета использованы, узел l остается нераскрашенным В конце фазы стек пуст, а ГК восстановлен и часть его узлов раскрашена 13.3 Глобальное распределение и назначение регистров 13.3.10 Алгоритм раскраски графа конфликтов 3 фаза. Проверка на окончание процесса раскраски Если нераскрашенных узлов не осталось, алгоритм завершается. Если часть узлов ГК осталась нераскрашенной, то для каждого такого узла либо генерируются команды сброса ( слив ), либо интервал жизни, соответствующий узлу расщепляется (на два или более подинтервалов), после чего ГК перестраивается с учетом слива и/или разделенных узлов. После перестройки ГК делается переход на первую фазу. Ключевым моментом является порядок в котором узлы ГК помещаются в стек. Наиболее распространенный эвристический критерий слива узла – минимум отношения узла степень сброса цена _ _ Найти ИЖ всех переменных, построить ГК , вычислить стоимость сброса для каждого ИЖ, выполнить раскраску ГК. После этого либо каждый ИЖ получит цвет ( положительный исход ), либо часть ИЖ останутся неокрашенными ( отрицательный исход ). В случае положительного исхода каждому ИЖ присваивается физический регистр В случае отрицательного исхода ГК перестраивается и снова выполняется раскраска ГК. Определение ИЖ Построение ГК Вычисление стоимости сброса Раскраска ГК Перестройка ГК Назначение регистров Раскраска получена 13.3 Глобальное распределение и назначение регистров 13.3.11 Структура распределителя регистров 13.3.12 Перестройка графа конфликтов 13.3 Глобальное распределение и назначение регистров Перестройка ГК достигается помимо слияния ИЖ (п. 13.3.9) с помощью сливания переменных (п. 13.3.13) и расщепления ИЖ (п.13.3.14). 13.3.13 Сливание переменных 13.3 Глобальное распределение и назначение регистров Сливание временной переменной t состоит в следующем: в «автоматической» памяти процедуры выделить ячейку ta для хранения значений t (эту ячейку называют «дом» t ); перед каждой командой, использующей t , вставить команду LD t, ta ; после каждой команды, определяющей t , вставить команду ST ta, t ; просматривают текст полученной процедуры с целью выявить и удалить лишние команды LD и ST (иногда это удается). 13.3.13 Сливание переменных 13.3 Глобальное распределение и назначение регистров ADD a, b, c UMN d, a ADD e, d, f MUL f, 2, e ADD b, d, e ADD e, e, 1 B 1 B 2 B 3 B 4 ADD b, f, c ADD a, b, c UMN d, a LD f, fa ADD e, d, f MUL f, 2, e ST fa, f ADD b, d, e ADD e, e, 1 B 1 B 2 B 3 B 4 LD f, fa ADD b, f, c d a b c e f ГК Хроматическое число 3 d a b c e f Хроматическое число 4 13.3.14 Расщепление интервалов жизни 13.3 Глобальное распределение и назначение регистров a и b в конфликте ADD a, m, 1 ADD b, k, 4 ADD r, b, m ADD a, m, 1 ADD a, m, 1 ST mem, a ADD b, k, 4 ADD r, b, m LD a, mem ADD a, m, 1 Конфликт между a и b устранен На левом рисунке LR a и LR b полностью пересекаются. Расщепив LR a на два LR , удается устранить конфликт. При этом команды ST и LD применяются только здесь, а не перед всеми a 13.3.15 Примеры глобального распределения регистров 1) Распределение виртуальных (символических) регистров a 2 b 3 d c e a g + c, 1 a < d b + b, 1 d * 2, d b < 10 d + d, 1 f + a, b g + e, g print(b,d,e,g) B 1 B 2 B 3 B 4 s1 2 s2 3 s3 c s4 s1 s5 + s3,1 s1 < s3 s2 + s2,1 s3 * 2,s3 s2 < 10 s3 + s3,1 s6 + s1,s2 s5 + s4,s5 print(s2,s3,s4,s5) B 1 B 2 B 3 B 4 13.3 Глобальное распределение и назначение регистров 13.3 Глобальное распределение и назначение регистров Применим слияние интервалов к команде копирования s4 = s1 ( в блоке B1 ). Получим s1 = 2 s2 = 3 s3 = c s5 = s3 + 1 s1 < s3 s2 = s2 + 1 s3 = 2 * s3 s2 < 10 s3 = s3 + 1 s6 = s1 + s2 s5 = s1 + s5 print(s2,s3,s1,s5) B 1 B 2 B 3 B 4 Оценим стоимости сброса для оставшихся символических регистров s1 , s2 , s3 , s5 и s6 Символич. регистр Стоимость сброса s1 2.0 s2 1.0 + 21.0 + 2.0 + 2.0 = 26.0 s3 6.0 + 20.0 + 4.0 + 2.0 = 32.0 s5 2.0 + 4.0 + 2.0 = 8.0 s6 Стоимость сброса вычисляется по формуле LR copy copy Depth LR use use Depth LR def def Depth CopyWt UseWt DefWt Spill_cost ) ( ) ( ) ( 10 10 10 где def , use и copy – отдельные команды определения, использования и копирования в LR , а DefWt , UseWt и CopyWt – стоимости соответствующих команд При вычислении стоимости сброса считается DefWt = UseWt = 2.0 , CopyWt = 1.0 Стоимость s6 = , так как регистр s6 – не является живым B 1 B 2 B 3 B 4 13.3 Глобальное распределение и назначение регистров 2) Построение графа конфликтов ( s1 , …, s6 – виртуальные регистры, R1, …, R5 – физические регистры ) s1 s2 s3 s4 s5 s6 R1 R2 R3 R4 R5 Все физические регистры считаются всегда живыми Пусть частота выполнения блоков B 1 , B 3 и B 4 равна 1, а частота выполнения блока B 2 равна 7 Каждому символическому регистру соответствует один интервал жизни, поэтому, например, LR a и s1 – синонимы На символических регистрах s1 , s2 , s3 , s4 хранятся значения, поэтому результаты всех вычислений в блоках B 2 и B 3 будем помещать на R5 13.3.15 Примеры глобального распределения регистров Матрица смежности графа конфликтов имеет вид 1 1 1 1 1 1 0 0 0 0 6 1 1 1 1 0 0 0 0 0 5 1 1 1 1 0 0 0 0 4 1 1 1 0 0 0 0 3 1 1 0 0 0 0 2 1 0 0 0 0 1 1 1 1 1 5 1 1 1 4 1 1 3 1 2 5 4 3 2 1 5 4 3 2 1 s s s s s s R R R R s s s s s R R R R R 13.3 Глобальное распределение и назначение регистров 13.3.15 Примеры глобального распределения регистров Граф конфликтов и его матрица смежности примут вид s1 s2 s3 s5 s6 R1 R2 R3 R4 R5 1 1 1 1 0 0 0 0 0 6 1 1 1 1 0 0 0 0 5 1 1 1 0 0 0 0 3 1 1 0 0 0 0 2 1 0 0 0 0 1 1 1 1 1 5 1 1 1 4 1 1 3 1 2 5 3 2 1 5 4 3 2 1 s s s s s R R R R s s s s R R R R R 13.3 Глобальное распределение и назначение регистров 13.3.15 Примеры глобального распределения регистров |