- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Анализ потока управления и потока данных в программе презентация
Содержание
- 1. Анализ потока управления и потока данных в программе
- 2. Содержание Структура компилятора Пример программы на
- 3. ядро компилятора Структура компилятора Компилятор -
- 4. int func( int a, int b)
- 5. 1. MOVE.s32 -> res // line:3,0
- 6. Граф потока управления
- 7. Граф потока управления
- 8. Граф потока управления с промежуточным представлением
- 9. Обход (нумерация) Обход в глубину (depth
- 10. Обязательное предшествование (доминирование)
- 11. Узел d доминирует/постдоминирует узел n если
- 12. Дерево доминаторов
- 13. Дерево постдоминаторов
- 14. Глубинное остовное дерево (depth-first spanning tree)
- 15. Глубинное остовное дерево (пример)
- 16. Выделение сильно связных подграфов
- 17. Разметка циклов
- 18. Дерево циклов
- 19. Несводимый цикл – цикл с более,
- 20. Компоненты с одним входом и одним выходом
- 21. Дерево структуры программы (program structure tree)
- 22. Классический анализ потока данных
- 23. Время жизни переменных
- 24. Итерационный алгоритм определения времени жизни переменных
- 25. Форма статического единственного присваивания Фрагмент программы
- 26. Форма статического единственного присваивания в виде Def-Use графа
- 27. Построение phi-функций Для каждой переменной определяем
- 28. CFG CFG+DOM Dominance Frontier Фронт
- 29. Хорошо зарекомендовавшая себя техника потокового анализа.
- 30. Классы эквивалентности: 1,2,3,4 Метод нумераций значений
- 31. int func( int a, int b)
- 32. 16 (с + d) подстановка констант
- 33. Литература к лекции
Содержание Структура компилятора Пример программы на С Линейная последовательность операций Анализ потока управления Анализ потока данных Примеры оптимизаций Литература к лекции Agenda
Слайд 2
Содержание
Структура компилятора
Пример программы на С
Линейная последовательность операций
Анализ потока управления
Анализ потока данных
Примеры
оптимизаций
Литература к лекции
Литература к лекции
Agenda
Слайд 3
ядро компилятора
Структура компилятора
Компилятор - переводит исходный код программы (написанные на языке
высокого уровня) в эквивалентный код на языке целевой платформы
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.Линкер
Слайд 4
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;
}
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;
}
Пример (исходый код программы на С)
Слайд 5
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 //
3. MOVE.s32
4. MOVE.s32
5. MOVE.s32
6. GOTO
7. LABEL //
…
52. IF bool_tvar.15,
53. LABEL //
54. MOVE.s32 res -> D.1572 // line:23,0
55. MOVE.s32 D.1572 -> D.1552 //
56. RETURN D.1552 //
Линейная последовательность операций
Слайд 9
Обход (нумерация)
Обход в глубину (depth first)
1. для каждого преемника {
2. устанавливаем
номер ++
3. обходим рекурсивно преемника }
Обход в ширину (reverse post order)
1. для каждого преемника {
2. обходим рекурсивно преемника }
3. устанавливаем номер --
Маркирование
Клонирование
Построение дерева доминаторов/постдоминаторов
Построение дерева циклов
3. обходим рекурсивно преемника }
Обход в ширину (reverse post order)
1. для каждого преемника {
2. обходим рекурсивно преемника }
3. устанавливаем номер --
Маркирование
Клонирование
Построение дерева доминаторов/постдоминаторов
Построение дерева циклов
Действия на графе потока управления
Слайд 11
Узел d доминирует/постдоминирует узел n если любой путь от стартового/стопового узла
к n проходит через d
Алгоритмы построения дерева доминаторов/постдоминаторов
Простейший алгоритм O(N*N)
Lengauer-Tarjan алгоритм O((N+E)log(N+E))
Алгоритмы построения дерева доминаторов/постдоминаторов
Простейший алгоритм O(N*N)
Lengauer-Tarjan алгоритм O((N+E)log(N+E))
Свойство доминирования/постдоминирования
Слайд 19
Несводимый цикл – цикл с более, чем одним входом
Цикл можно свести
путем дублирования кода
Несводимые циклы
Слайд 25
Форма статического единственного присваивания
Фрагмент программы
z = 3;
if(P)
{
y = 5;
} else
{
y =
z + 2;
}
x = y;
}
x = y;
SSA - форма
z = 3
if(P)
y1=5
y2=z+2
y3=phi(y1,y2)
x=y3
Слайд 27
Построение phi-функций
Для каждой переменной определяем узлы cfg, в которых она инициализируется
Запускаем
алгоритм поиска итерационного фронта доминирования (сложность O(|N|*|DF|)*B/size(word))
N – количество узлов в графе потока управления
DF – итерационный фронт доминирования для одного узла (в среднем 1-2 на задачах)
B – количество переменных
size(word) – размер слова в битовом векторе
По результатам работы алгоритма строим phi-функции
Линковка записей и чтений
N – количество узлов в графе потока управления
DF – итерационный фронт доминирования для одного узла (в среднем 1-2 на задачах)
B – количество переменных
size(word) – размер слова в битовом векторе
По результатам работы алгоритма строим phi-функции
Линковка записей и чтений
Построение SSA/Def-Use графа
Слайд 28
CFG CFG+DOM Dominance Frontier
Фронт доминирования
START
STOP
d
STOP
START
J-дуги
дуги дерева доминаторов
b
START
STOP
Слайд 29
Хорошо зарекомендовавшая себя техника потокового анализа.
Анализ присваивает одинаковые номера операциям, вырабатывающие
одинаковые значения. Номера называются классами эквивалентности.
Алгоритмическая сложность O(N * D * Argmax)
N количество операций
D глубина дерева циклов
Argmax максимальное число аргументов у операции
Алгоритмическая сложность O(N * D * Argmax)
N количество операций
D глубина дерева циклов
Argmax максимальное число аргументов у операции
Метод нумераций значений
Слайд 30
Классы эквивалентности: 1,2,3,4
Метод нумераций значений (пример)
A = i;
B = j;
A =
j + 100;
B = i + 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”
Слайд 31
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;
}
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;
}
Исходый код программы
Слайд 32
16 (с + d) подстановка констант
11,13 (a+b) сбор общих подвыражений
13,18
(b+i) удаление частично избыточных вычислений
20 (k++) удаление избыточных вычислений
11 (a+b) вынос инвариантных вычислений из цикла
20 (k++) удаление избыточных вычислений
11 (a+b) вынос инвариантных вычислений из цикла
Примеры оптимизаций
