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

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

Оптимизация компиляторов 14.11.06

Сегодня будет некоторое представление программы, которое удобно для анализа и оптимизации:

SSA-representation.

Static Single assignment – статическое однократное присваивание.

Основная идея: каждая переменная может присваиваться тоько один раз. Но так как языки процедурные, имеют циклы.. то возникают некоторые интересные эффекты.

По результату анализа достигающих определений мы можем построить du- и ud-цепочки.

Если у нас далее в тексте программы бужет использована переменная х, то для этой же самой переменной мы будем строить ссылки на те же самые точки. Что у нас получается: у нас некрая переменная n раз исп и m раз опред, то ссылко будет максимум N*M. Представление, в котором исп du-цепочки, неэффективно по памяти. Хотелось бы её снизить или преодолеть.

value numbering:

a <- x+y

b <- a-1

a <- y+b

b <- x*4

a <- a+b

Три раза присв а, два раза b.

Введём поняте поколения перменных. Каждое присваивание порождает новое поколение переменных.

a1 <- x+y

b1 <- a-1

a2 <- y+b

b2 <- x*4

a3 <- a2+b2

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

Пример:

b <- M[x]

a <- 0

if b<4

| \

V _|

a<-b c<-a+b

фи-функция:

a_k = fi(a_i1, ... a_ij)

Выбирает то поколение, по которому пути мы пришли в потоке управления.

С учётом этого программа будет выглядеть след образом:

b1 <- M[x]

a1 <- 0

if b1 < 4

| \

V _|

a2 <- b1 a3 <- fi(a2, a1)

c1 <- a2 + b1

Фи-функция для нек перем – все переменные, когда мы рассм анализ достиг определений, то там были пары... (...), которые могут быть в этом месте

Такое представление, в котором есть поколения переменных, каждое поколение может присв один раз, называется SSA-r.

Фи функцию мы можем рассм, которая транформирует входные аргументы в выходные.

Поскольку мы знаем, что каждая перем присв один раз, то многие оптимизации становятся проще, и можно многие оптимизации применять.

Вопросы:

Если мы будем ставить фи функции везде, где неск перем сливаются в одну, то выигрыша мы не получим. Вопрос –

1. как расставить минимальное количество фи-функций?

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

Рассмотрим:

<картинка>

value numbering

1. существует х

2. существует у

3. существует Рxz x волнистая стрелка z

4. существует Рyz y волнистая стрелка z

5. Pxz пересечение Pyz = {z}

6. после отбрасывания посл верш z у Pxz и Pyz не должно быть общих вершин

Критерии слияния путей

Проверять этот критерий очень сложно.

Нужен более простой критерий. Его можно найти, используя

Граница доминирования (domination frontier)

Пусть есть граф потока управления b. ГД DF(b) – множество {x | существует y принадлежит pred(x), b dom y, b !dom x}

(рисуется граф потока управления)

Рассмотрим 4. Блок 4 находится в границе доминир для 5, то же самое 13, 12.

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

В 13и 12 фи-функция от 3 арг, в 4 – от 2. Но, как показано ранее, фи-функции тоже явл присваиванием. Поэтому нужно рассмотреть эти новые присваивания и добавить фи-функции на граници доминир тех блоков, в которые мы добавили фи-функции. Соотв, нам потребуется не простая, а итерир граница доминирования, под которой мы понимаем транзитивное замыкание.

Алгоритм построения SSA:

1. Найти итерир гр доминирования

2. Найдя опред, расставить фи-функции

3. При первонач установке фи-функций поколения не устанавливаются, поэтому мы должны назначить поколения

Вычисление границы доминирования

Мы предполагаем, что у нас уже есть дерево доминирования, соответственно, как мы её можем вычислять. Введём две вспомогательных переменных, n – номер базового блока. DF_loc(n) – множество последователей блока n, которые не доминируются базовым блоком n = succ(n) \ {x: n dom x}. Требуется вспомог функция DF_up(n) – все вершины граници доминирования n, которые не доминируются непосредственным доминатором n.

Тогда границу доминир для n можно определить след образом:

DF(n) = DF_loc(n) объединение (объединение по всем c принадлежит children(n) DF_up(c))

Как мы будем вычислять границы доминирования:

compute DF(n)

s <- {}

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

if idom(y) != n

S объединить равно {y}

foreach c принадлежит children(n)

compute DF(c)

foreach w принадлежит DF(c)

if !(n dom w)

s принадлежит равно {w}

DF(n) = s

Втоорой шаг

insert Phi

foreach n

foreach a принадлежит Aorig(n) //Aorig – множество перем, поред в данном базовом блоке изначально

defsites(а) объединить равно {n}

foreach a

w = defsites(a)

while (w != пусто)

n = get(w)

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

if y != Afi(a)

a = fi(a..a) by

Afi(a) объединить равно {y}

С помощью такого алгоритма мы будем добавлять функции в базовые блоки.

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

Алгоритм занимает листочек, поэтому мы этого делать не будем

Оптимизация в Ssa-представлении:

1. устранение мёртвого кода (dead-code elimination)

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

   a_k <- F(v₁ ... v_m)

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

2. Продвижение констант

   Если есть присваивание вида a <- const, и если мы знаем, что значение перем не меняется, то мы можем заменить в этом месте перем за константу. Можно заменить фи-функцию, у которой все аргументы – одинаковые константы, её можно заменить на константу. Как только мы поставили константы, может потребоваться вычисление выражения, если там одни константы.

3. Продвижение копий

   y_i <- x_i

   v_k <- fi(x_i, x_i, ..., x_i)

Задача обратного преобразования:

Надо избавиться от фи-функций.

амый тривиальный способ – вводить дополнительный код но очевидно, что это никому неинтересно.

По опред, фи функции находятся в точках слияния путеё.

xi = fi(x1, x2, x3)

Простейший способ – перенести присваивание вверх:

x1 <-x1 xi <- x2 xi <- x3

\ | /

_| V |_

edge splitting

Для начала добавим пустой базовый блок.

Алгоритм неправильный, так делать нельзя.

Пример:

x0 <- 1

|

V /____

x1 <- fi(x0, x2) \ |

y <- x1 |

x2 <- 2 __|

|

V

return y

Сделаем copy propagation:

x0 <- 1

|

V /____

x1 <- fi(x0, x2) \ |

x2 <- 2 __|

|

V

return x1

Расщепляем фи-функцию:

x0 <- 1

x1 <- x0

|

V /____

x1 <- x2 \ x1 <- x2

| ____________|

|

V

return x1

Пример плохой. Придумать пример самим.

Другой пример:

x0 <- 1

y0 <- 2

|

V /____

x1 <- fi(x0, x2) \ |

y1 <- fi(y0, y2) |

y2 <- x1 |

x2 <- 3 __|

|

V

x0 <- 1

y0 <- 2

|

V /____

x1 <- fi(x0, x2) \ |

y1 <- fi(y0, y2) |

x2 <- 3 __|

|

V

x0 <- 1

y0 <- 2

x1 <- x0

y1 <- y0

|

V /____

x2 <- 3 \ x1 <- x2

| _______________y1 <- x1

|

V