Анализ потока управления и потока данных в программе

Содержание
Структура компилятора
Пример программы на С
Линейная последовательность операций
Анализ потока управления
Анализ потока данных
Примеры оптимизаций
Литература к лекции
Agenda

ядро компилятора
Структура компилятора
Компилятор - переводит исходный код программы (написанные на языке высокого уровня) в эквивалентный код на языке целевой платформы
Compiler structure
.c
.cpp
.f77
...
.c
.cpp
.F
...
High-Level IR
High-Level IR
High-Level IR
Low-Level
IR
Low-Level
IR
Low-Level IR
asm
.o
.obj
.out
.exe
1
2
4
5
6
1.Препроцессор
2.Front-End
3.Оптимизации
4.Кодогенератор
5.Ассемблер
6.Линкер

int func( int a, int b)
{
int res = 0;
int c = 10;
int d = 20;
int i, j, k = 0;
for ( i = 0; i < 100; i++ )
{
for ( j = 0; j < 100; j++ )
{
if ( i + j < a + b )
{
res += a + b + i;
} else
{
res += c + d + j;
}
res += b + i;
}
k++;
}
return res;
}
Пример (исходый код программы на С)

1. MOVE.s32
-> res // line:3,0
2. MOVE.s32
-> c // line:4,0
3. MOVE.s32
-> d // line:5,0
4. MOVE.s32
-> k // line:6,0
5. MOVE.s32
-> i // line:8,0
6. GOTO
// line:8,0
7. LABEL //
…
52. IF bool_tvar.15,
,
// line:8,0
53. LABEL //
54. MOVE.s32 res -> D.1572 // line:23,0
55. MOVE.s32 D.1572 -> D.1552 //
56. RETURN D.1552 //
Линейная последовательность операций

Граф потока управления

Граф потока управления

Граф потока управления с промежуточным представлением

Обход (нумерация)
Обход в глубину (depth first)
1. для каждого преемника {
2. устанавливаем номер ++
3. обходим рекурсивно преемника }
Обход в ширину (reverse post order)
1. для каждого преемника {
2. обходим рекурсивно преемника }
3. устанавливаем номер --
Маркирование
Клонирование
Построение дерева доминаторов/постдоминаторов
Построение дерева циклов
Действия на графе потока управления

Обязательное предшествование (доминирование)

Узел d доминирует/постдоминирует узел n если любой путь от стартового/стопового узла к n проходит через d
Алгоритмы построения дерева доминаторов/постдоминаторов
Простейший алгоритм O(N*N)
Lengauer-Tarjan алгоритм O((N+E)log(N+E))
Свойство доминирования/постдоминирования

Дерево доминаторов

Дерево постдоминаторов

Глубинное остовное дерево (depth-first spanning tree)

Глубинное остовное дерево (пример)

Выделение сильно связных подграфов

Разметка циклов

Дерево циклов

Несводимый цикл – цикл с более, чем одним входом
Цикл можно свести путем дублирования кода
Несводимые циклы

Компоненты с одним входом и одним выходом

Дерево структуры программы (program structure tree)

Классический анализ потока данных

Время жизни переменных

Итерационный алгоритм определения времени жизни переменных

Форма статического единственного присваивания
Фрагмент программы
z = 3;
if(P)
{
y = 5;
} else
{
y = z + 2;
}
x = y;
SSA - форма
z = 3
if(P)
y1=5
y2=z+2
y3=phi(y1,y2)
x=y3

Форма статического единственного присваивания в виде Def-Use графа

Построение phi-функций
Для каждой переменной определяем узлы cfg, в которых она инициализируется
Запускаем алгоритм поиска итерационного фронта доминирования (сложность O(|N|*|DF|)*B/size(word))
N – количество узлов в графе потока управления
DF – итерационный фронт доминирования для одного узла (в среднем 1-2 на задачах)
B – количество переменных
size(word) – размер слова в битовом векторе
По результатам работы алгоритма строим phi-функции
Линковка записей и чтений
Построение SSA/Def-Use графа

CFG CFG+DOM Dominance Frontier
Фронт доминирования
START
STOP
d
STOP
START
J-дуги
дуги дерева доминаторов
b
START
STOP

Хорошо зарекомендовавшая себя техника потокового анализа.
Анализ присваивает одинаковые номера операциям, вырабатывающие одинаковые значения. Номера называются классами эквивалентности.
Алгоритмическая сложность O(N * D * Argmax)
N количество операций
D глубина дерева циклов
Argmax максимальное число аргументов у операции
Метод нумераций значений

Классы эквивалентности: 1,2,3,4
Метод нумераций значений (пример)
A = i;
B = j;
A = j + 100;
B = i + 100;
foo += a[i] + (3*A + 2*B);
bar += a[j] + (7*B – 2*A);
i++; j++;
if ( i % 2)
return (foo – bar);
foo = bar = 0;
j = i = 0;
1
2
3
4
“0”

int func( int a, int b)
{
int res = 0;
int c = 10;
int d = 20;
int i, j, k = 0;
for ( i = 0; i < 100; i++ )
{
for ( j = 0; j < 100; j++ )
{
if ( i + j < a + b )
{
res += a + b + i;
} else
{
res += c + d + j;
}
res += b + i;
}
k++;
}
return res;
}
Исходый код программы

16 (с + d) подстановка констант
11,13 (a+b) сбор общих подвыражений
13,18 (b+i) удаление частично избыточных вычислений
20 (k++) удаление избыточных вычислений
11 (a+b) вынос инвариантных вычислений из цикла
Примеры оптимизаций