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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Анализ потока управления и потока данных в программе, слайд №1Анализ потока управления и потока данных в программе, слайд №2Анализ потока управления и потока данных в программе, слайд №3Анализ потока управления и потока данных в программе, слайд №4Анализ потока управления и потока данных в программе, слайд №5Анализ потока управления и потока данных в программе, слайд №6Анализ потока управления и потока данных в программе, слайд №7Анализ потока управления и потока данных в программе, слайд №8Анализ потока управления и потока данных в программе, слайд №9Анализ потока управления и потока данных в программе, слайд №10Анализ потока управления и потока данных в программе, слайд №11Анализ потока управления и потока данных в программе, слайд №12Анализ потока управления и потока данных в программе, слайд №13Анализ потока управления и потока данных в программе, слайд №14Анализ потока управления и потока данных в программе, слайд №15Анализ потока управления и потока данных в программе, слайд №16Анализ потока управления и потока данных в программе, слайд №17Анализ потока управления и потока данных в программе, слайд №18Анализ потока управления и потока данных в программе, слайд №19Анализ потока управления и потока данных в программе, слайд №20Анализ потока управления и потока данных в программе, слайд №21Анализ потока управления и потока данных в программе, слайд №22Анализ потока управления и потока данных в программе, слайд №23Анализ потока управления и потока данных в программе, слайд №24Анализ потока управления и потока данных в программе, слайд №25Анализ потока управления и потока данных в программе, слайд №26Анализ потока управления и потока данных в программе, слайд №27Анализ потока управления и потока данных в программе, слайд №28Анализ потока управления и потока данных в программе, слайд №29Анализ потока управления и потока данных в программе, слайд №30Анализ потока управления и потока данных в программе, слайд №31Анализ потока управления и потока данных в программе, слайд №32Анализ потока управления и потока данных в программе, слайд №33
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Анализ потока управления и потока данных в программе. Доклад-сообщение содержит 33 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 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; }
Описание слайда:
Пример (исходый код программы на С) 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 //
Описание слайда:
Линейная последовательность операций 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. устанавливаем номер -- Маркирование Клонирование Построение дерева доминаторов/постдоминаторов Построение дерева циклов
Описание слайда:
Действия на графе потока управления Обход (нумерация) Обход в глубину (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))
Описание слайда:
Свойство доминирования/постдоминирования Узел 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


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

Слайд 26


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

Слайд 27


Построение SSA/Def-Use графа Построение phi-функций Для каждой переменной определяем узлы cfg, в которых она инициализируется Запускаем алгоритм поиска итерационного фронта доминирования (сложность O(|N|*|DF|)*B/size(word)) N – количество узлов в графе потока управления DF – итерационный фронт доминирования для одного узла (в среднем 1-2 на задачах) B – количество переменных size(word) – размер слова в битовом векторе По результатам работы алгоритма строим phi-функции Линковка записей и чтений
Описание слайда:
Построение 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
Описание слайда:
Фронт доминирования CFG CFG+DOM Dominance Frontier

Слайд 29


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

Слайд 30


Метод нумераций значений (пример) Классы эквивалентности: 1,2,3,4
Описание слайда:
Метод нумераций значений (пример) Классы эквивалентности: 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; }
Описание слайда:
Исходый код программы 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) вынос инвариантных вычислений из цикла
Описание слайда:
Примеры оптимизаций 16 (с + d) подстановка констант 11,13 (a+b) сбор общих подвыражений 13,18 (b+i) удаление частично избыточных вычислений 20 (k++) удаление избыточных вычислений 11 (a+b) вынос инвариантных вычислений из цикла

Слайд 33


Литература к лекции
Описание слайда:
Литература к лекции

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию