Презентация Анализ потока управления и потока данных в программе онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Анализ потока управления и потока данных в программе абсолютно бесплатно. Урок-презентация на эту тему содержит всего 33 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:33 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:1.01 MB
- Просмотров:64
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Новиков Сергей
№2 слайд
Содержание слайда: Содержание
Структура компилятора
Пример программы на С
Линейная последовательность операций
Анализ потока управления
Анализ потока данных
Примеры оптимизаций
Литература к лекции
№3 слайд
Содержание слайда: Структура компилятора
Компилятор - переводит исходный код программы (написанные на языке высокого уровня) в эквивалентный код на языке целевой платформы
№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;
}
№5 слайд
Содержание слайда: Линейная последовательность операций
1. MOVE.s32 <s32:0> -> res // line:3,0
2. MOVE.s32 <s32:10> -> c // line:4,0
3. MOVE.s32 <s32:20> -> d // line:5,0
4. MOVE.s32 <s32:0> -> k // line:6,0
5. MOVE.s32 <s32:0> -> i // line:8,0
6. GOTO <mo_l0:#nil> // line:8,0
7. LABEL //
…
52. IF bool_tvar.15, <mo_l0:#nil>, <mo_l0:#nil> // 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 //
№6 слайд
Содержание слайда: Граф потока управления
№7 слайд
Содержание слайда: Граф потока управления
№8 слайд
Содержание слайда: Граф потока управления с промежуточным представлением
№9 слайд
Содержание слайда: Действия на графе потока управления
Обход (нумерация)
Обход в глубину (depth first)
1. для каждого преемника {
2. устанавливаем номер ++
3. обходим рекурсивно преемника }
Обход в ширину (reverse post order)
1. для каждого преемника {
2. обходим рекурсивно преемника }
3. устанавливаем номер --
Маркирование
Клонирование
Построение дерева доминаторов/постдоминаторов
Построение дерева циклов
№10 слайд
Содержание слайда: Обязательное предшествование (доминирование)
№11 слайд
Содержание слайда: Свойство доминирования/постдоминирования
Узел d доминирует/постдоминирует узел n если любой путь от стартового/стопового узла к n проходит через d
Алгоритмы построения дерева доминаторов/постдоминаторов
Простейший алгоритм O(N*N)
Lengauer-Tarjan алгоритм O((N+E)log(N+E))
№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 слайд
Содержание слайда: Построение SSA/Def-Use графа
Построение phi-функций
Для каждой переменной определяем узлы cfg, в которых она инициализируется
Запускаем алгоритм поиска итерационного фронта доминирования (сложность O(|N|*|DF|)*B/size(word))
N – количество узлов в графе потока управления
DF – итерационный фронт доминирования для одного узла (в среднем 1-2 на задачах)
B – количество переменных
size(word) – размер слова в битовом векторе
По результатам работы алгоритма строим phi-функции
Линковка записей и чтений
№28 слайд
Содержание слайда: Фронт доминирования
CFG CFG+DOM Dominance Frontier
№29 слайд
Содержание слайда: Метод нумераций значений
Хорошо зарекомендовавшая себя техника потокового анализа.
Анализ присваивает одинаковые номера операциям, вырабатывающие одинаковые значения. Номера называются классами эквивалентности.
Алгоритмическая сложность O(N * D * Argmax)
N количество операций
D глубина дерева циклов
Argmax максимальное число аргументов у операции
№30 слайд
Содержание слайда: Метод нумераций значений (пример)
Классы эквивалентности: 1,2,3,4
№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;
}
№32 слайд
Содержание слайда: Примеры оптимизаций
16 (с + d) подстановка констант
11,13 (a+b) сбор общих подвыражений
13,18 (b+i) удаление частично избыточных вычислений
20 (k++) удаление избыточных вычислений
11 (a+b) вынос инвариантных вычислений из цикла
№33 слайд
Содержание слайда: Литература к лекции
Скачать все slide презентации Анализ потока управления и потока данных в программе одним архивом:
