Базы данных
<<  Создание однотабличной базы данных Методы анализа данных  >>
Анализ потока управления и потока данных в программе
Анализ потока управления и потока данных в программе
Содержание
Содержание
Структура компилятора
Структура компилятора
int func( int a, int b) { int res = 0; int c = 10; int d = 20; int i,
int func( int a, int b) { int res = 0; int c = 10; int d = 20; int i,
1. MOVE
1. MOVE
Граф потока управления
Граф потока управления
Граф потока управления
Граф потока управления
Граф потока управления с промежуточным представлением
Граф потока управления с промежуточным представлением
Действия на графе потока управления
Действия на графе потока управления
Обязательное предшествование (доминирование)
Обязательное предшествование (доминирование)
Свойство доминирования/постдоминирования
Свойство доминирования/постдоминирования
Дерево доминаторов
Дерево доминаторов
Дерево постдоминаторов
Дерево постдоминаторов
Глубинное остовное дерево (depth-first spanning tree)
Глубинное остовное дерево (depth-first spanning tree)
Глубинное остовное дерево (пример)
Глубинное остовное дерево (пример)
Выделение сильно связных подграфов
Выделение сильно связных подграфов
Разметка циклов
Разметка циклов
Дерево циклов
Дерево циклов
Несводимые циклы
Несводимые циклы
Компоненты с одним входом и одним выходом
Компоненты с одним входом и одним выходом
Дерево структуры программы (program structure tree)
Дерево структуры программы (program structure tree)
Классический анализ потока данных
Классический анализ потока данных
Время жизни переменных
Время жизни переменных
Итерационный алгоритм определения времени жизни переменных
Итерационный алгоритм определения времени жизни переменных
Форма статического единственного присваивания
Форма статического единственного присваивания
Форма статического единственного присваивания в виде Def-Use графа
Форма статического единственного присваивания в виде Def-Use графа
Построение SSA/Def-Use графа
Построение SSA/Def-Use графа
Фронт доминирования
Фронт доминирования
Метод нумераций значений
Метод нумераций значений
Метод нумераций значений (пример)
Метод нумераций значений (пример)
int func( int a, int b) { int res = 0; int c = 10; int d = 20; int i,
int func( int a, int b) { int res = 0; int c = 10; int d = 20; int i,
Примеры оптимизаций
Примеры оптимизаций
Литература к лекции
Литература к лекции

Презентация: «Анализ потока управления и потока данных в программе». Автор: Google. Файл: «Анализ потока управления и потока данных в программе.ppt». Размер zip-архива: 902 КБ.

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

содержание презентации «Анализ потока управления и потока данных в программе.ppt»
СлайдТекст
1 Анализ потока управления и потока данных в программе

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

Новиков Сергей

2 Содержание

Содержание

Agenda

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

3 Структура компилятора

Структура компилятора

Compiler structure

.c .cpp .f77 ...

.c .cpp .F ...

.o .obj

.out .exe

Low-Level IR

Low-Level IR

1.Препроцессор 2.Front-End 3.Оптимизации 4.Кодогенератор 5.Ассемблер 6.Линкер

Компилятор - переводит исходный код программы (написанные на языке высокого уровня) в эквивалентный код на языке целевой платформы

Ядро компилятора

High-Level IR

Low-Level IR

asm

High-Level IR

High-Level IR

1

2

4

5

6

4 int func( int a, int b) { int res = 0; int c = 10; int d = 20; int i,

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

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)

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

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

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

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

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

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

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

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

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

19 Несводимые циклы

Несводимые циклы

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

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

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

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

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

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

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

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

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

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

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

25 Форма статического единственного присваивания

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

Фрагмент программы 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

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

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

27 Построение SSA/Def-Use графа

Построение 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

START

START

START

d

b

STOP

STOP

STOP

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

J-дуги

29 Метод нумераций значений

Метод нумераций значений

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

30 Метод нумераций значений (пример)

Метод нумераций значений (пример)

“0”

Классы эквивалентности: 1,2,3,4

1

foo = bar = 0; j = i = 0;

3

2

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++;

4

if ( i % 2)

return (foo – bar);

31 int func( int a, int b) { int res = 0; int c = 10; int d = 20; int i,

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 Литература к лекции

Литература к лекции

«Анализ потока управления и потока данных в программе»
http://900igr.net/prezentacija/informatika/analiz-potoka-upravlenija-i-potoka-dannykh-v-programme-240132.html
cсылка на страницу
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Базы данных > Анализ потока управления и потока данных в программе