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

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

Чернов 07.11.06

Reaching definitions

worklist – список необработанных вершин

На 0й итерации в worklist записываем все вершины.

WL <- V

while (WL!=0)

v <- get(WL)

out'_v = FLOW_v(объединение по всем w принадлежащим pred(v) out_w)

if (out'_v!=out_v) WL <-WL объединить с succ(v)

порядок выбора произвольный.

Такой способ обработки применяется во многих алгоритмов, в планировщике инструкций.

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

<COL WIDTH=64*> <COL WIDTH=64*> <COL WIDTH=128*> <THEAD> </THEAD> <TBODY> </TBODY>

0	Func fib(m)
1	f0 <- 0
2	f1 <- 1
3	if m > 1 goto L3
4	@1 <- m
5	goto L2
6	L1: if i<=m goto L3
7	@1 <= f2
8	goto L2
9	L3: f2 <- f0+1
10	f0 <- f1
11	f1 <- f2
12	i <- i+1
13	goto L1
14	L2: return @1

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

Хранить это накладно.

Du-chains

ud-chains

use-def chain

В ud-цепочке будут храниться достигающие определения. Для f1 в 12 это будет 10 и 2.

du-цепочка – обратная цепочка – def-use цепочка. Мы делаем наоборот. Для каждого, например, берём какое-нибудь определение, например, определение переменной f0, и для каждого определения строим, и она будет состоять из использования её в 9 инстр. Для m это 3, 4, 6. То есть если ud-цепочка это отображения точек исп в точки определния, то ду – обратная.

Du-ud-chains – один из исп методов хранения инф.

Анализ достигающих опред относится к прямым итеративным методам. Теперь рассмотр пример обратного метода – обратный анализ потоков данных.

Live variables

Пусть есть переменная в программе, и точка в программе. <v, i>

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

Предп, эта переменная занимает регистр процессора, хранится на некотором регистре процессора. Если анализ живых перем показал, что она далее нигде не исп, то это означает, что регистр мы можем использовтаь для других целей, и освободить его под другие переменные. Решение задачи необх для качественного распред регистров, мы распред регитры на то время, когда она используется. Такая задача часто возн для счётчиков перем циклов. Например, етсь цикл по i:

for (i=...) {...}

for (j=...) {...}

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

Как она решается:

Что из себя представляет вершина exit. Рассмотрим функцию, котора не имеет побочного эффекта, как, напр, функция фибоначчи

Вершина exit – 14 инструкция, где возвращ регистр @1. На exit информация о живых переменных не определена. На входе в return живой будет переменная @1. То есть, вообще говоря, в точке, предшевствующей оператор return, то эта переменная живая. В вершиеу exit есть несколько переходовЖ из инстр 4 и из инстр 7. На выходе множество живых переменных состоит из @1​ Рассм каждую инстр. Рассм каждую инстр. Что будет на входе. Очевидно, что @1 не будет жив выше 7, и выше 4. Но вместо него мы должны потр, чтобы переменная f2 и m были живыми, соотв. То есть определна переменная потока, которая из out получает in. Чему она равна. Нам нужно ихз множ живых перем выкинуть перем, которые переприсв в данной точке и добавить к множ живых перем множ используемых: FLOWi(OUTi)=OUTi\GENi объединить с USEi. Мы можем свести упр всей программы к графу потока упрЮ на каждом графе можно посчитать FLOW, и у нас в резте появится некоторое уравнение потоков данных для решения задачи о живых переменных.

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

//Какой-то рисунок, Микез вроде его перерисовал...

OUTi=Inj объединение с Ink

OUTi = объединение по всем послед вершинам i j=succ(i) Inj

Эту задачу решать или простой итерацией, или с помощью списка необраб вершин.

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

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

В прошлый раз возник вопрос о том, как быстро пработают алгоритмы, и заврешаются ди они вообще. Можно зделать вцывод, что они заверш. Какой-то разумной оценки сделать не получится. А теперь алгебр основы:

Теория решёток (lattice)

Решётка – неекая алгебр структура, опред множеством элементов произв природы и две операции. Первую опреацию обозначю таким образом П, такую - таким образом |_|. Первая называется meet, вторую – join. Эти опреации определны на всём множестве элементов решётки.

Любое x, y принадлежит L: существует единств u? Z: u = x П y, z = x |_| y

Требования:

1. Коммутативеость

x П y = y П x

x |_| y = y |_| x

2. Ассоциативность

(x П y) П z = x П (y П z)

(x |_| y) |_| z = x |_| (y |_| z)

3. Наличие двух выделенных элементов – inf и sup

_|_ - bottom

T – top

x П _|_ = _|_

x |_| T = T

Поскольку дополн даны дистриб свойства, то говорят о дистриб решётках.

Если выполн

(x П y) |_| z = (x |_| y) П (y |_| z)

(x |_| y) П z = (x П y) |_| (y П z)

то такая решётка называется дистрибутивной.

Примеры:

BV3 – битовые вектора длины 3

meet П - &

join |_| - |

_|_ = <000>

T = <111>

При таком опред выполн все свойства, и кроме того эта решётка дистрибутивна.

Решётки, если они не очень большие, то их удобно предст графически в виде некоторого графа.

Операции meet и join индуцируют частичный порядок. А именно, мы можем ввести отношение частичного порядка т и тт, когда их joiun будет давать один из эл-тов:

x квадратик без правой стороны с двойной нижней y <=> x П y = x

x квадратик без левой стороны с двойной нижней y <=> x |_| y = x

Поскольку есть отн частичного порядка, мы можем ввести понятие высоты решётки, а именно:

v₀ = _|_ -> v₁ -> v₂ -> ... -> v_n-1 -> T = v_n

причем v_i квадратик без правой стороны с двойной нижней v_i+1

n – высота решётки

Если есть некая ф-ция в них самих, то мы можем ставить задачу о неподвиж точке на решётке, то есть x0 такое, что x0 = f(x0). Потребуем, чтобы f была монотонной, то есть для любого x: f(x) квадратик без левой стороны с двойной нижней x, Мы можем ввести понятие эффективной высоты решётки относительно f. Что это такое. Ну, как. Через n-кратное применение f мы обозначим

f⁽⁰⁾(x)=x

f⁽ⁱ⁾(x)=f(f^(i-1)(x))

x0 квадратик без правой стороны с двойной нижней f(x0) квадратик без правой стороны с двойной нижней f⁽²⁾(x0) квадратик без правой стороны с двойной нижней ... квадратик без правой стороны с двойной нижней f^(k)(x0) = f^(k+1)(x0)

max по x0 (min по k) – эффективнаЯ высота решётки.

Сверху эффективная высота решётки ограничена высотой решётки.

В чём смысл f. Если мы рассм задачу анализа потоков данных, то мы увидим, что имели дело с решётками, По сути, мы имели дело с решётками битовых векторов некрого размера BVn, мы использовали join и meet и f – некоторая функция потока. И для задачи достиг опред, и для живых перем функция монотонна. Следовательно, время работы будет оцениваться эффект высотой решётке. А в следствие того, что эфф высота оценивается просто высотой, а высота равна n. Мы получаем, что для реш задач нам нужно проделать не бдолее n итераций. Таким образом, мы можем достаточно грубо оценить сверху время работы алгоритма.

Какое есть ещё здесь замечание:

Рассм некрую общую задачу анализа потоков данных.

Пусть у нас есть неуий нграф потока управления. (рисует баянистый граф)

Нам нужно найте все вектора meet-over-all-path solution. Фикс базовый блок. В этот блок ведёт некоторое количество путей. Соотв, на каждом из этих путей мы можем насчитать некоторое множество In_p1 на нашем пути. Рассм другое множество, насчитаем In_p2 ... In_pk. Как нам теперь получить решение задачи потоков данных? Нам нужно будет взять минимум этих решений.

In = П по p:entry -> B₅ Inp

То эсть это практически невозможно.

То, что мы делали в прошлый раз – находили макс решение неподвиж точки – maximum-fixed point solution.

Как соотн то решение, которое мы находили, с задачей потока данных.

Оказывается, если решётка дистрибутивная, а функия монотонная:

f – дистрибутивная

L – монотонная

тогда MFP-solution = MOP-solution (минимума по всем путям)

То есть свойства дистриб ф и монот решёт дают дост условия для конечности работы.

Далеко не все решётки являются дистрибутивными.

Можем в качестве пример рассм решётку о продвижении констант – constant propagation

Мы хотим по нашей программе, если у нас есть используемые константы, то есть присваиваем переменной константу, и дальше эту перем исп, то мы можем перем заменить на константу.

Решётка будет выглядить след образом. Предп, что рассм булевские и целые значения. Явные элементы top и bottom:

T – переопределённость – значение переменной константа, но какая, мы не знаем.

/ | \

... -2 -1 false 0 true 1 2 ...

\ | /

_|_ - неопределённость

Решётка будет иметь высоту два, но воттакую структуру

Для этой решётки свойство дистриб не выполняется.

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