Введение в теорию построения оптимизирующих компиляторов, 08 лекция (от 21 ноября)

Материал из eSyr's wiki.

Чернов, 21.11.06

Расстановка поколений переменных.

Определние границ доминир

Простановка границ доминир шаблонов для фи-функций

Переименрвание. т. е. расстановка поколений.

Первый случай:

Использование переменной не в фи-функции. Использование а

Таким образом, для расст поколений мы можем делать обход нашей функции согластно дереву доминирования. Как только мы в процессе длерева доминирования попадаем в базовый блок, мы обрабатывем его линейно, и как только нам попадается переменная, мы назначаем ей поколение и заносим стек. Как только она попадается ещё раз, мы берём её из стека и перенумеровываем.

Когда мы обрабатываем очередной базовый блок, мы просматриваем каждую исходящую дугу, и проставляем поколение в соотв со стеком. Нам нужен счётчик поколений и стек поколений.

Init

foreach a принадлежит Vans

count[a] <- 0

stack[a] <- empty

stack[a].push(0)

Rename(n)

Запускать расстановук поколений мы должны с корня дерева. Делаем первый проход.

Rename(n)

foreach s принадлежит stmt(n)

if s != фи-финкция

foreach x принадлежит use(s)

i <- stack[x].top()

заменить x на x_i

foreach a принадлежит defs(s)

count[a]++

i <- count[a]

stack[a].push(i)

заменить a на a_i

На этом просмотр переменных заканчивается.

Предположим,

foreach y принадлежит succ(n)

пусть n – j-й предш. для y

foreach фи принадлежит фи-функция(y)

пусть a- j-й операнд

i <- stack[a].top()

заменить а на a_i

for x принадлежит child(n)

Rename(x)

//ну и последнее, совсем последнее – почистить стек

foreach s прниадлежит stmt(n)

foreach a принадлежит def(j)

stack[a].pop();

проблемы:

1. когда возникают перекрывающиеся интервалы жизни переменных (требуется edge splitting)

2. Параллельна янатура всех фи-присваиваний – все фи-присв одновременны

3. Нарушение границ доминирования
   
   

Распределение регистров

1. register allocation

2. register assignment

В многих Яп есть конструкции или переменные, которые не имеет смысла помещать в регистр. Например, переменные у которых беруться адреса, переменные, слишком большие для регистров.

Для всех переменных, которые будут помещаться на регистры, мы назначим временный регистр, псевдорегистр, при этом исходим из предположения, что их неогр количество.

Для назн регистров нам нужна инф, жива перем или нет, следовательно, предварительно нужен анализ живых переменных.

Если переменная не жива, то в этой точке программы мы можем повторно использовать регистр, на которую она распределена.

Какие переменные не могут одновременно помещены на регистр – которые одновременно живы.Каждую переменную, которая исп. в программе, представляем вершиной графа. Регистры также предст. вершинами. Если две переменные одновременно не являются живыми, то мы их соединяем. Такой граф называется графом наложений.

Теперь поставим в соотв регистру цвет. Соответственно, две перем не могут иметь одного цвета. Эта задача широко известна – задача о раскраске графа. Нас интересует раскраска с мин. количеством цветов. Это NP-полная задача. Тем не менее, можно применять эфристики.

Несколько дополнительных замечаний:

На самом деле, переменные исрпользовать не очень хорошо. Это накладывает лишние ограничения.

Поэтому распред регистров лучше вести для сетей (web)

Что такое сеть – предположим, что есть построенные du-цепочки (можно обобщитьна SSA). Пусть есть опред x, от него есть ссылки на места использования. У этого использования есть, возможно на него ссылкаются другие определения. Соответственно, максимальная компонента и будет являться сетью.

Именно компоненты связности двудольного графа должны рассм.при распред на регистры. Т. о. прежде, чем выполнятьанализ живых переменных, нам нужно провести сети.

Второе замечание. Переменные не могут попадать на один регистр тогда, когда они не явл. одновременно живыми. Но это приводит к большому количеству дуг. Пример:

Можно ослабить этот критерий.

(я прослушал, как он звучит :( Похоже, что надо смотреть только на точки определения)

В соответствии с ним гв графе будут только два ребра, соед а1 а2 и b1 b2.

При распред регистров Необходимо учитывать требования архитектуры.

Соглашения по вызовам функций. Например, если известно, что нек-рые регистры после вызова функции пользоваться, то нужно соед их дугами с всеми живыми в точке вызова перем, чтобы исключить их нахождение там. Или например. перем цикла должна быть на опред регистре.

Для преобр. графа можно склеивать регистры (register coalescing)

ai <- aj

1. Либо ai и aj не накладываются друг на друга, либо они не исп. от текущей точки до конца функции. В этом случае их можно склеить

   => def ai -> def aj удаляем ai <- aj

Склецйка регистров:

1. Выполняем edge splitting

2. <IMG SRC="CO_06_11_21_html_528d24d7.gif" ALIGN=LEFT>a3=a1 a3=a2

3. <IMG SRC="CO_06_11_21_html_70a6898f.gif" ALIGN=LEFT><IMG SRC="CO_06_11_21_html_m3a7159c4.gif" ALIGN=LEFT> В резульатте появляется множество лишних копирований, что может поставить под вопрос саму целесообразность преобразования.

Раскраска графа наложений:

Пусть у нас есть R регистров

1. Вершины степени меньше R – всегда могут быть раскрашены, выкидываем их, так можно удалять, пока не останутя только вершины степени больше равно R

   2. Найдём произв узел со степенью больше равно R, найдём ту, для которой отношение стоимости сброса к её степени минимальна. Стоимость сброса – то, насколько плохо запихивать переменную в память.Такую вершину мы, как и все со степенью меньше R помещаем в стек. Это мы делаем, пока граф не опустошится. 3. Теперь их будем выимать и назначать цвета. Если назначили, то всё хорошо, если же нет, то в опред момент появляется переменная, которая становится кандидатом на сброс.

   В чё мзаключается сброс (spill).