Тема 13 2018Распределение_и_назначение. 13. Распределение и назначение регистров 13. 1
 Скачать 0.73 Mb.
|
|
13.2.4 Пример t , u и v – временные переменные, локальные для блока, а , b , с и d – переменные, живые при выходе из блока. Генерация кода для базового блока: 1 t -, a, b 2 u -, a, c 3 v +, t, u 4 a d 5 d +, v, u Сгенерированный код: LD R1, a LD R2, b SUB R2, R1, R2 LD R3, c SUB R1, R1, R3 ADD R3, R2, R1 LD R2, d ADD R1, R3, R1 ST a, R2 ST d, R1 Код содержит 4 команды LD 2 команды ST Все эти команды связаны с множествами In(B) и Out(B) переменных живых при входе в блок B и при выходе из него 6 команд из 10 связаны с обращениями к памяти 13.2 Локальное распределение регистров 13.2.5 Реализация функции getReg R 1 R 2 R 3 d a v a b c d t u v a, R 2 b c d, R 1 R 3 i i i i o o o o f Генерация команды для инструкции I х op, y, z выбор регистров для операндов y и z выбор регистра для результата х Выбор регистра R y для операнда y ( регистр R z для операнда z выбирается аналогично) . Если DA[y] ссылается на регистр R , то полагаем R у = R Если DA[y] не содержит ссылок на регистры, но имеется регистр R, для которого D [ R ] не содержит ссылок ни на одну переменную, то полагаем R у = R 13.2 Локальное распределение регистров 13.2.5 Реализация функции getReg Выбор регистра R y для операнда y Если DA[y] не содержит ссылок на регистры и не имеется ни одного регистра R , для которого DR[R] не содержит ссылок ни на одну переменную, то R можно использовать в качестве R у , если для каждой переменной v , ссылка на которую содержится DR[R] , выполняется одно из следующих условий: DA[v] содержит ссылку не только на R , но и на адрес v , v представляет собой переменную х , вычисляемую командой I , и х не является одновременно одним из операндов команды I , переменная v после команды I больше не используется. Если ни одна из перечисленных выше ситуаций не имеет места, то прежде чем использовать R в качестве R у , необходимо выполнить сброс регистра , т.е. команду ST v, R 13.2 Локальное распределение регистров 13.2.5 Реализация функции getReg Выбор регистра R x для результата x Если DR[R] ссылается только на х , то полагаем R х = R Это можно делать даже тогда, когда х является одним из у или z , так как в одной машинной команде допускается совпадение двух регистров. Если y не используется после команды I и если DR[R y ] ссылается только на y , то R y может использоваться в роли R x Если z не используется после команды I и если DR[R z ] ссылается только на z , то R z может использоваться в роли R x Генерация команд для инструкции I х у Сначала выбирается R y , как и для операнда инструкции х op, y, z , после чего полагается R x = R y 13.2 Локальное распределение регистров В примере на рисунке независимое назначение регистров в базовых блоках привело к тому, что для одной и той же переменной x в каждом блоке используются разные регистры Если бы getReg блока B 3 знала, что в блоке B 1 значение x было получено на R7 , то выделила бы для x регистр R7 , что позволило бы исключить команду загрузки на регистр в блоке B 3 Наличие блоков B 2 и B 4 еще больше усложняет проблему, так как возникают различные требования на разных путях 13.2.6 Ограничения ST x, R7 B 1 ST x, R3 B 2 LD R2, x B 3 LD R4, x B 4 Интервалом жизни (ИЖ) значения w переменной v называется множество команд программы, начиная с команды, в которой переменная v определяется со значением w , и кончая последней командой, в которой переменная v используется с этим значением 0 LD R0 … | R 0 [0,10] 1 LD R1 R0(0) | R 1 [1,6] 2 LD R2 2 | R 1 [6,7] 3 LD R3 R0(@x) | R 1 [7,8] 4 LD R4 R0(@y) | R 1 [8,9] 5 LD R5 R0(@z) | R 1 [9,10] 6 MUL R1 R1 R2 | R 2 [2,6] 7 MUL R1 R1 R3 | R 3 [3,7] 8 MUL R1 R1 R4 | R 4 [4,8] 9 MUL R1 R1 R5 | R 5 [5,9] 10 ST v R0(0) | 13.3.1 Интервалы жизни 13.3 Глобальное распределение и назначение регистров 13.3.2 Построение интервалов жизни Построение множеств переменных, живых на выходе из каждого блока. Это задача анализа потока данных. Методом итераций решается система уравнений (1) где LiveOut(B) – множество переменных, живых на выходе из B , LiveIn(B) – множество переменных, живых на входе в B , use(B) – множество переменных блока B , которые используются в B до их переопределения в B , VarKill B – множество переменных блока B , которые переопределяются в B ( оно обозначалось как def B ). Решив методом итераций систему ( 1), получим LiveOut(B) для всех B . ) ( )) ] [ ( ( ] [ B Succ s S S VarKill S LiveOut use B LiveOut 13.3 Глобальное распределение и назначение регистров 13.3.2 Построение интервалов жизни Исследование отношений между различными определениями и использованиями Нужно построить множества всех определений, достигающих одного и того же использования ( UD-цепочки ), и всех использований, которые достигаются одним и тем же определением ( DU-цепочки ). Такое построение удобно проводить в SSA - форме, так как в ней каждое имя определяется только один раз, каждое использование ссылается на единственное имя, а объединение имен обеспечивается с помощью - функций. Для программы в SSA - форме требуемая группировка имен достигается за один просмотр. Алгоритм объединения имен анализирует каждую - функцию и строит объединение множеств, связанных с каждым ее параметром, и множества, связанного с определяемой ею переменной. Это объединение и представляет интервал жизни. После обработки всех - функций строится отображение SSA - имен на имена интервалов жизни. 13.3 Глобальное распределение и назначение регистров 13.3 Глобальное распределение и назначение регистров 13.3.3 Построение интервалов жизни. Пример … a 0 … b 0 … … b 0 d 0 … c 0 … … d 1 c 0 d 2 ( d 0 , d 1 ) … a 0 … d 2 B 0 B 1 B 2 B 3 … LR a … LR b … … LR b LR d … LR c … … LR d LR c … LR a … LR d B 0 B 1 B 2 B 3 Фрагмент кода в SSA - представлении Тот же фрагмент, переписанный в терминах интервалов жизни LR a = {a 0 } LR b = {b 0 } LR c = {c 0 } LR d = = {d 0 ,d 1 ,d 2 } 13.3 Глобальное распределение и назначение регистров 13.3.4 Оценка стоимости сброса Стоимость сброса складывается из следующих трех компонент: стоимость вычисления адресов при сбросе стоимость операций доступа к памяти оценка частоты выполнения Для хранения сброшенных значений во фрейме процедуры выделяется специальная область. Это позволяет свести к минимуму стоимость вычисления адресов при сбросе, исключив использование косвенной адресации и дополнительных регистров для вычисления адреса сбрасываемого значения. Интервал жизни, который содержит только команды загрузки регистра и его сохранения может иметь отрицательную стоимость сброса в случае, когда обе команды обращаются к одному и тому же адресу памяти. Такие ситуации могут возникнуть вследствие исключения избыточных вычислений. 13.3 Глобальное распределение и назначение регистров 13.3.4 Оценка стоимости сброса Чтобы учитывать частоту выполнения базовых блоков в графе потока управления, каждый базовый блок снабжается аннотацией , содержащей оценку стоимости его выполнения (профилирование) Для получения грубой оценки стоимости частоты выполнения используется простая эвристика : делается допущение, что каждый цикл выполняется 10 раз; тогда стоимость каждой загрузки внутри одного цикла оценивается как 10, внутри гнезда из двух циклов – как 100 и т.д.; стоимость каждой ветви непредсказуемого if-then-else оценивается как 0.5. На практике из этой эвристики, в частности, следует, что сброс выгоднее выполнять в более внешнем цикле. Аннотации могу вычисляться заранее (и тогда потребуется дополнительный просмотр программы), либо во время первого обращения 13.3 Глобальное распределение и назначение регистров 13.3.5 Конфликтные ситуации и граф конфликтов При распределении регистров моделируется состязание за место на регистрах целевой машины. Рассмотрим два различных интервала жизни LR i и LR j . Если в программе существуют команды, во время которых и LR i , и LR j актуальны, то они не могут занимать один и тот же регистр В таком случае говорят, что LR i и LR j находятся в конфликте. Определение. Интервалы жизни LR i и LR j находятся в конфликте если один из них актуален при определении другого и они имеют различные значения Граф, узлы которого соответствуют отдельным интервалам жизни, а дуги соединяют интервалы жизни, находящиеся в конфликте , называется графом конфликтов (ГК). Этот граф не является направленным, так как отношение нахождения в конфликте симметрично. Таким образом, если два узла ГК являются смежными ( соединены дугой), то им должны соответствовать различные регистры 13.3 Глобальное распределение и назначение регистров 13.3.6 Раскраска графа Раскраска произвольного графа G состоит в присвоении каждому узлу G определенного цвета таким образом, чтобы любым двум смежным узлам G не были сопоставлены одинаковые цвета. Раскраска, использующая n цветов называется n - раскраской, а наименьшее из таких n называется хроматическим числом графа На рисунке внизу хроматическое число левого графа равно 2, а правого графа – 3. Проблема нахождения хроматического числа графа и проблема выяснения , допускает ли граф n - раскраску NP- полны. A B C D E A B C D E Если у целевого компьютера n регистров, то проблема их распределения для программы сводится к проблеме построения n - раскраски ГК В частности, для данного примера ГК допускает 2- раскраску , следовательно , достаточно 2 регистров Фрагмент кода с именами интервалов жизни Граф конфликтов … LR a … LR b … … LR b LR d … LR c … … LR d LR c … LR a … LR d B 0 B 1 B 2 B 3 LR a LR b LR c LR d 13.3 Глобальное распределение и назначение регистров 13.3.7 Раскраска графа конфликтов Если оптимизирующая фаза компилятора переставила две последние команды блока B 1 Тогда LR b будет живым при определении LR d , и значит в ГК необходимо добавить дугу ( LR b , LR d ) в результате чего ГК уже не будет допускать 2- раскраску, так как ( LR a , LR b и LR d должны быть разного цвета ) Фрагмент кода с именами интервалов жизни Граф конфликтов … LR a … LR b … LR d … … LR b LR c … … LR d LR c … LR a … LR d B 0 B 1 B 2 B 3 Теперь у распределителя регистров две возможности : 1 : Использовать третий регистр 2: Перед определением регистра для LR d сбросить LR a или LR b LR a LR b LR c LR d 13.3 Глобальное распределение и назначение регистров 13.3.7 Раскраска графа конфликтов 13.3 Глобальное распределение и назначение регистров 13.3.8 Построение графа конфликтов После построения глобальных интервалов жизни и множеств LiveOut для каждого базового блока можно за один просмотр программы от Exit к Entry построить ГК. Внутри каждого базового блока алгоритм поддерживает множество LiveNow переменных, живых в текущей точке блока. При входе в блок B полагают LiveNow = LiveOut(B) Затем просматривают каждую команду блока ( op LR a , LR b , LR c ) и узел ГК, соответствующий переменной LR a , определяемой в этой команде, соединяют дугами со всеми узлами , соответствующими переменным из LiveNow (это как раз переменные, живые во время определения другой переменной). Для повышения эффективности ГК задается левой ( нижней) половиной своей матрицы смежности. Операции копирования |