Kafe-sviaz.ru

Финансовый журнал
9 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Анализ потока управления

Анализ потока управления

Анализ потока управления — это статический анализ кода для определения порядка выполнения программы. Порядок выполнения выражается в виде графа потока управления.

Для многих языков граф потока управления явно прослеживается в исходном коде программы. Как результат, анализ потока управления обычно относится статическому анализу кода. В ходе анализа определяются приемники функций и методов, вызванных программами, написанными на языках высокого уровня. И для языков функционального программирования, и для объектно-ориентированных языков программирования термин «Анализ потока управления» означает алгоритм, который формирует граф потока управления.

Термин анализ потока управления (control flow analysis) был впервые использован Нейлом Джонсом (Neil D. Jones) [1] и Олином Шиверсом (Olin Shivers) [2] .

Для анализа потока управления могут быть использованы: Абстрактная интерпертация (англ.), Удовлетворение ограничений, Типизация данных.

Примечания

  1. Neil D. Jones (1981), ««Flow analysis of lambda expressions»», Automata, Languages and Programming: 114–128 , DOI 10.1007/3-540-10843-2_10
  2. Shivers, Olin (1988), ««Control-flow analysis in Scheme»», Proceedings of the ACM SIGPLAN’88 Conference on Programming Language Design and Implementation (PLDI), SIGPLAN Notices, Vol.23, No.7: 164–174 , DOI 10.1145/53990.54007

Wikimedia Foundation . 2010 .

Смотреть что такое «Анализ потока управления» в других словарях:

Граф потока управления — Простые графы потока управления[1] Граф потока управления (англ. … Википедия

Анализ портфельных рисков — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей … Википедия

анализ — 3.8.7 анализ (review): Деятельность, предпринимаемая для установления пригодности, адекватности и результативности (3.2.14) рассматриваемого объекта для достижения установленных целей. Примечание Анализ может также включать определение… … Словарь-справочник терминов нормативно-технической документации

АНАЛИЗ ДЬЮРЕЙШН — DURATION ANALYSISАНАЛИЗ АКТИВОВ/ПАССИВОВ, к рый включает измерение изменений стоимости реального основного капитала, возникающих в результате определенных изменений процентных ставок. Термин дьюрейшн был предложен в 1938 г. Маколеем (Macauley), к … Энциклопедия банковского дела и финансов

Управления автоматизированная система — (АСУ) совокупность экономико математических методов, технических средств (ЭВМ, средств связи, устройств отображения информации, передачи данных и т.д.) и организационных комплексов, обеспечивающих рациональное управление сложным объектом… … Большая советская энциклопедия

Мониторинг и анализ сетей — Мониторинг сетей целенаправленное воздействие на сеть, осуществляемое для организации ее функционирования по заданной программе: включение и отключение системы, каналов передачи данных, терминалов, диагностика неисправностей, сбор… … Википедия

ГОСТ 15895-77: Статистические методы управления качеством продукции. Термины и определения — Терминология ГОСТ 15895 77: Статистические методы управления качеством продукции. Термины и определения оригинал документа: 2.30. k я порядковая статистика x(k) Определения термина из разных документов: k я порядковая статистика 2.44.… … Словарь-справочник терминов нормативно-технической документации

Теория управления — Теория управления наука о принципах и методах управления различными системами, процессами и объектами. Основами теории управления являются кибернетика и теория информации. Суть теории управления состоит в построении математической модели на … Википедия

ПРОТОЧНО-ИНЖЕКЦИОННЫЙ АНАЛИЗ — (ПИА), авто матизир. метод анализа и исследования в потоке. При этом точный микрообъем (пробу) изучаемой жидкости вводят в непрерывно движущийся по направлению к детектору поток инертного носителя (или р ра реагента). В потоке образуется зона… … Химическая энциклопедия

Реверс органов управления самолета — (от латинского revrsus обращенный назад) явление, обусловленное потерей эффективности аэродинамических органов управления и обращением их действия. Р. наступает главным образом из за упругости авиационных конструкций. Например, для прямого крыла… … Энциклопедия техники

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

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

Содержание Структура компилятора Пример программы на С Линейная последовательность операций Анализ потока управления Анализ потока данных Примеры оптимизаций Литература к лекции 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 ->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”

Анализ потока управления

Для многих языков граф потока управления явно прослеживается в исходном коде программы. Как результат, анализ потока управления обычно относится статическому анализу кода. В ходе анализа определяются приемники функций и методов, вызванных программами, написанными на языках высокого уровня. И для языков функционального программирования, и для объектно-ориентированных языков программирования термин «Анализ потока управления» означает алгоритм, который формирует граф потока управления

Читать еще:  Анализ курса доллара на неделю

Термин анализ потока управления (control flow analysis) был впервые использован Нейлом Джонсом (Neil D. Jones) [1] и Олином Шиверсом (Olin Shivers) [2]

Для анализа потока управления могут быть использованы: Абстрактная интерпертация (англ.), Удовлетворение ограничений, Типизация данных

Примечания

  1. Neil D. Jones (1981), ««Flow analysis of lambda expressions»», Automata, Languages and Programming: 114–128 , DOI 10.1007/3-540-10843-2_10 &#160 ;
  2. Shivers, Olin (1988), ««Control-flow analysis in Scheme»», Proceedings of the ACM SIGPLAN’88 Conference on Programming Language Design and Implementation (PLDI), SIGPLAN Notices, Vol.23, No.7: 164–174 , DOI 10.1145/53990.54007 &#160 ;

Wikimedia Foundation . 2010 .

См. также в других словарях:

Граф потока управления — Простые графы потока управления[1] Граф потока управления (англ. … Википедия

Анализ портфельных рисков — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей … Википедия

анализ — 3.8.7 анализ (review): Деятельность, предпринимаемая для установления пригодности, адекватности и результативности (3.2.14) рассматриваемого объекта для достижения установленных целей. Примечание Анализ может также включать определение… … Словарь-справочник терминов нормативно-технической документации

АНАЛИЗ ДЬЮРЕЙШН — DURATION ANALYSISАНАЛИЗ АКТИВОВ/ПАССИВОВ, к рый включает измерение изменений стоимости реального основного капитала, возникающих в результате определенных изменений процентных ставок. Термин дьюрейшн был предложен в 1938 г. Маколеем (Macauley), к … Энциклопедия банковского дела и финансов

Управления автоматизированная система — (АСУ) совокупность экономико математических методов, технических средств (ЭВМ, средств связи, устройств отображения информации, передачи данных и т.д.) и организационных комплексов, обеспечивающих рациональное управление сложным объектом… … Большая советская энциклопедия

Мониторинг и анализ сетей — Мониторинг сетей целенаправленное воздействие на сеть, осуществляемое для организации ее функционирования по заданной программе: включение и отключение системы, каналов передачи данных, терминалов, диагностика неисправностей, сбор… … Википедия

ГОСТ 15895-77: Статистические методы управления качеством продукции. Термины и определения — Терминология ГОСТ 15895 77: Статистические методы управления качеством продукции. Термины и определения оригинал документа: 2.30. k я порядковая статистика x(k) Определения термина из разных документов: k я порядковая статистика 2.44.… … Словарь-справочник терминов нормативно-технической документации

Теория управления — Теория управления наука о принципах и методах управления различными системами, процессами и объектами. Основами теории управления являются кибернетика и теория информации. Суть теории управления состоит в построении математической модели на … Википедия

ПРОТОЧНО-ИНЖЕКЦИОННЫЙ АНАЛИЗ — (ПИА), авто матизир. метод анализа и исследования в потоке. При этом точный микрообъем (пробу) изучаемой жидкости вводят в непрерывно движущийся по направлению к детектору поток инертного носителя (или р ра реагента). В потоке образуется зона… … Химическая энциклопедия

Реверс органов управления самолета — (от латинского revrsus обращенный назад) явление, обусловленное потерей эффективности аэродинамических органов управления и обращением их действия. Р. наступает главным образом из за упругости авиационных конструкций. Например, для прямого крыла… … Энциклопедия техники

Формальные методы — Пример формальной спецификации с использованием Z нотации В информатике и инженерии программного обеспечения формальными методами называется группа техник, основанных на математическом аппарате для … Википедия

оценка — 3.9 оценка (evaluation): Систематическое определение степени соответствия объекта установленным критериям. Источник: ГОСТ Р ИСО/МЭК 12207 99: Информационная технология. Процессы жизненного цикла программных средств … Словарь-справочник терминов нормативно-технической документации

Гэп — (Gap) Гэп это разрыв цены в потоке котировок на графике между двумя свечами Определение гэпа, виды и причины возникновения гэпов, проведение анализа и торговля на рынке Форекс с использованием гэпов, графики гэпов Содержание >>>>>>>>>>> … Энциклопедия инвестора

Читать еще:  Как анализировать таблицы

Недостижимый код — В программировании и теории компиляторов, недостижимым кодом называют часть кода программы, которая ни при каких условиях не может быть исполнена, поскольку является недостижимой в графе потока управления[1][2]. Недостижимый код часто относят к… … Википедия

Оптимизирующий компилятор — Эта статья предлагается к удалению. Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/24 декабря 2012. Пока процесс обсужден … Википедия

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

Презентация на тему Анализ потока управления и потока данных в программе, предмет презентации: Разное. Этот материал содержит 33 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас — поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

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

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

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

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

int func( int a, int b)
<
int res = 0;
int c = 10;
int d = 20;
int i, j, k = 0;
for ( i = 0; i

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)

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

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

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

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

Форма статического единственного присваивания в виде 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

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

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

Ссылка на основную публикацию
Adblock
detector