Тема 13 2018Распределение_и_назначение. 13. Распределение и назначение регистров 13. 1
 Скачать 0.73 Mb.
|
|
R1 стек Граф конфликтов до исключения узлов R1 , R2 , R3 , R4 Граф конфликтов после исключения узлов R1 , R2 , R3 , R4 13.3 Глобальное распределение и назначение регистров 13.3.15 Примеры глобального распределения регистров Теперь узел R5 имеет меньше пяти смежных узлов; заталкиваем и его в стек и удаляем из графа конфликтов. Получается граф, изображенный на правом рисунке s1 s2 s3 s5 s6 стек Граф конфликтов до исключения узла R5 Граф конфликтов после исключения узла R5 s1 s2 s3 s5 s6 R5 R5 R4 R3 R2 R1 13.3 Глобальное распределение и назначение регистров 13.3.15 Примеры глобального распределения регистров Теперь все оставшиеся узлы графа конфликтов имеют меньше пяти смежных узлов; заталкиваем их (в произвольном порядке) в стек и удаляем из графа конфликтов. s1 s2 s3 s5 s6 стек s1 s2 s3 s5 s6 R5 R4 R3 R2 R1 13.3 Глобальное распределение и назначение регистров 13.3.15 Примеры глобального распределения регистров Выталкиваем регистры из стека и присваиваем каждому свободный цвет (всего имеется пять цветов). R5 имеет 4 смежных узла: s1 ( 1 ), s2 ( 2 ), s3 ( 3 ) и s6 ( 5 ). Следовательно, ему можно присвоить цвет 4 (только он свободен). стек s1 s2 s3 s5 s6 R5 R4 R3 R2 R1 Регистр Цвет s1 1 s2 2 s3 3 s5 4 s6 5 R5 4 R4 1 R3 2 R2 3 R1 5 R4 = 2 R3 = 3 R2 = c R5 = R2 + 1 R4 < R2 R3 = R3 + 1 R2 = 2 * R2 R3 < 10 R2 = R2 + 1 R1 = R4 + R3 R5 = R4 + R5 print(R3,R2,R4,R5) B 1 B 2 B 3 B 4 13.3 Глобальное распределение и назначение регистров 13.3.15 Примеры глобального распределения регистров 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – метод линейного сканирования ( Linear scan) Пусть доступно R регистров и пусть составлен список из n интервалов жизни. Алгоритм Linear scan должен распределить на регистры как можно больше ИЖ таким образом, чтобы никакие пересекающиеся ИЖ не были распределены на один и тот же регистр. Если n > R и ИЖ пересекаются в некоторой точке, то по крайней мере n − R ИЖ должны быть размещены в памяти. Количество пересекающихся ИЖ изменяется только в начале и в конце одного из ИЖ. Все ИЖ помещаются в список, отсортированный по возрастанию их начал. Тогда алгоритм может быстро просмотреть все ИЖ, перескакивая с одного начала ИЖ к следующему. На каждом шагу алгоритм поддерживает список активных ИЖ, которые пересекаются в данной точке и уже размещены на регистрах. Этот список активных поддерживается отсортированным по возрастанию концов входящих в него ИЖ. 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – метод линейного сканирования ( Linear scan) На псевдокоде active {} for each live interval i в порядке возрастания начал ExpireOldIntervals(i)//окончание старых интервалов if length(active) = R then SpillAtInterval(i) //слив интервала i else register[i] регистр, удаляемый из пула свободных регистров добавить i в active, отсортированный по возрастанию концов ИЖ 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – метод линейного сканирования ( Linear scan) На псевдокоде ExpireOldIntervals(i) foreach interval j in active, in order of increasing end point if endpoint[j] ≥ startpoint[i] then remove j from active add register[j] to pool of free registers return 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – метод линейного сканирования ( Linear scan) На псевдокоде SpillAtInterval(i) spill last interval in active if endpoint[spill] > end point[i] then register[i] register[spill] location[spill] new stack location remove spill from active add i to active, sorted by increasing end point else location[i] new stack location 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – метод линейного сканирования ( Linear scan) При обнаружении каждого нового ИЖ алгоритм просматривает список active с начала до конца. Во время просмотра из списка удаляются все закончившиеся ИЖ (ИЖ, которые больше не пересекаются, так как конец одного из них раньше начала другого) и делает соответствующий регистр доступным для распределения. 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – метод линейного сканирования ( Linear scan) Пример. Пусть доступно всего два регистра r1 и r2 v1 v2 v3 v4 v5 (1) v1 = 10 (2) v2 = 20 (3) v3 = v1 + v2 (4) v4 = v2 + v3 (5) v1 = v3 + v4 (6) v5 = v4 + v1 (7) return (v1 + v5) ИЖ обрабатываются в порядке v1,v2,v3,v4,v5. Сначала список Active пуст. На первом шаге обрабатывается ИЖ v1 Так как список Active пуст , регистр r1 выделяется для v1, и v1 заносится в список Active 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – метод линейного сканирования ( Linear scan) Пример. Пусть доступно всего два регистра r1 и r2 v1 v2 v3 v4 v5 (1) v1 = 10 (2) v2 = 20 (3) v3 = v1 + v2 (4) v4 = v2 + v3 (5) v1 = v3 + v4 (6) v5 = v4 + v1 (7) return (v1 + v5) ИЖ обрабатываются в порядке v1,v2,v3,v4,v5. После первого шага список Active содержит ИЖ v1. На втором шаге обрабатывается ИЖ v2 Так как v1 продолжает оставаться активным, v1 не исключается из списка Active, и для ИЖ v2 выделяется единственный свободный регистр r2, а v2 заносится в список Active 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – метод линейного сканирования ( Linear scan) Пример. Пусть доступно всего два регистра r1 и r2 На рисунках показано состояние до и после третьего шага. v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 r1 r2 m1 r2 r1 (1) (2) (3) (4) (5) (6) (7) Cписок Active:v1,v2 Cписок Active:v2,v3 Слито в память:m1 Текущий шаг 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – метод линейного сканирования ( Linear scan) Пример. Пусть доступно всего два регистра r1 и r2 Полученное распределение регистров показано на рисунке. Метод раскраски графа конфликтов обеспечивает для рассмотренного примера лучшее распределение регистров. (1) v1 = 10 (2) v2 = 20 (3) v3 = v1 + v2 (4) v4 = v2 + v3 (5) v1 = v3 + v4 (6) v5 = v4 + v1 (7) return (v1 + v5) (1) m1 = 10 (2) r2 = 20 (3) r1 = m1 + r2 (4) r2 = r2 + r1 (5) m1 = r1 + r2 (6) r1 = r2 + m1 (7) return (m1 + r1) 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – метод линейного сканирования ( Linear scan) Пример. Пусть доступно всего два регистра r1 и r2 Метод раскраски графа конфликтов обеспечивает для рассмотренного примера лучшее распределение регистров. (1) v1 = 10 (2) v2 = 20 (3) v3 = v1 + v2 (4) v4 = v2 + v3 (5) v1 = v3 + v4 (6) v5 = v4 + v1 (7) return (v1 + v5) (1) r2 = 10 (2) r1 = 20 (3) r2 = r2 + r1 (4) r1 = r1 + r2 (5) r2 = r2 + r1 (6) r1 = r1 + r2 (7) return (r2 + r1) Но метод раскраски графа конфликтов имеет асимптотическую временную сложность O ( n 2 ). Метод линейного сканирования реализует распределение регистров за один просмотр текста программы и имеет асимптотическую временную сложность O ( n ). 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – метод линейного сканирования ( Linear scan) Разработчики JIT- компиляторов (например, для языка Java или для языка Python ) предпочитают метод линейного сканирования. В отличие от метода раскраски графа конфликтов, имеющего асимптотическую временную сложность O ( n 2 ) , метод линейного сканирования реализует распределение регистров всего за один просмотр текста программы и имеет асимптотическую временную сложность O ( n ). В последнее время используется модификация метода линейного сканирования, называемая Second Chance Binpacking . Во многих случаях она позволяет увеличить точность линейного сканирования, сохраняя асимптотическую временную сложность O ( n ). 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – метод линейного сканирования ( Linear scan) Разработчики JIT- компиляторов (например, для языка Java или для языка Python ) предпочитают метод линейного сканирования. В отличие от метода раскраски графа конфликтов, имеющего асимптотическую временную сложность O ( n 2 ) , метод линейного сканирования реализует распределение регистров всего за один просмотр текста программы и имеет асимптотическую временную сложность O ( n ). В последнее время используется модификация метода линейного сканирования, называемая Second Chance Binpacking Во многих случаях она позволяет увеличить точность линейного сканирования, сохраняя асимптотическую временную сложность O ( n ) . Рассмотрим кратко этот метод. 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – модифицированный метод линейного сканирования (Second Chance Binpacking) Одним из основных недостатков метода линейного сканирования является тот факт, что он не рассматривает возможных «дыр» в ИЖ. В то же время анализ ГПУ реальных программ показывает, что такие дыры нередко возникают в связи с многочисленными ветвлениями. Даже простой пример, рассмотренный выше, подтверждает это. В самом деле ИЖ для v1 имеет дыру от инструкции (3) до инструкции (5): значение v1 == 10 после инструкции (3) не используется, а в инструкции (5) переопределяется. (1) v1 = 10 (2) v2 = 20 (3) v3 = v1 + v2 (4) v4 = v2 + v3 (5) v1 = v3 + v4 (6) v5 = v4 + v1 (7) return (v1 + v5) 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – модифицированный метод линейного сканирования (Second Chance Binpacking) В самом деле ИЖ для v1 имеет дыру от инструкции (3) до инструкции (5): значение v1 == 10 после инструкции (3) не используется, а в инструкции (5) вообще переопределяется. Методу линейного сканирования, (1) v1 = 10 (2) v2 = 20 (3) v3 = v1 + v2 (4) v4 = v2 + v3 (5) v1 = v3 + v4 (6) v5 = v4 + v1 (7) return (v1 + v5) который игнорирует этот факт, приходится и после инструкции (3) хранить в памяти (так как регистров не хватает) мертвое значение v1 В модифицированном методе реализована возможность расщепления ИЖ. Эта возможность позволяет расщепить ИЖ v1 на два ИЖ – v11 и v12. В итоге v1 получает второй шанс занять регистр. Отметим, что если бы использовалась SSA- форма, расщепления бы не потребовалось, оно бы произошло автоматически. 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – модифицированный метод линейного сканирования (Second Chance Binpacking) В модифицированном алгоритме ИЖ v1 сначала помещается в список Active , на третьем шаге переводится в список Inactive , а на пятом шаге снова помещается в список Active В итоге получается распределение регистров, показанное на рисунке. (1) v1 = 10 (2) v2 = 20 (3) v3 = v1 + v2 (4) v4 = v2 + v3 (5) v1 = v3 + v4 (6) v5 = v4 + v1 (7) return (v1 + v5) r1 = 10 r2 = 20 r1 = r1 + r2 r2 = r2 + r1 r1 = r1 + r2 r2 = r2 + r1 return (r1 + r2) v1 v2 v3 v4 v5 r1 r2 r1 r2 r2 13.3 Глобальное распределение и назначение регистров 13.3.11 Быстрый алгоритм распределения регистров – модифицированный метод линейного сканирования (Second Chance Binpacking) Модифицированный алгоритм имеет примерно такую же скорость, как и базовый алгоритм линейного сканирования, и при этом генерирует код примерно такого же качества, что и алгоритм раскраски графа конфликтов. |