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

Презентация:



Advertisements
Похожие презентации
Анализ потока управления. Линейные участки (basic blocks, базовые блоки) Линейный участок – это максимальная последовательность инструкций, такая что:
Advertisements

Внутреннее представление компилятора Типы представлений и их особенности.
Анализ Потока Данных Итеративные алгоритмы и SSA.
Оптимизация управляющего графа программ, имеющих избыточные условные вычисления Выполнил: Степнов Денис, 816 гр. Научный руководитель: Бучнев А.Ю. Выпускная.
Информатика ЕГЭ Уровень А5. Вариант 1 Определите значения переменных a, b, c после выполнения следующего фрагмента программы: a:=5; b:=1; a:=a+b; if a>10.
ВОССТАНОВЛЕНИЕ ТЕКСТА ФОРТРАН-ПРОГРАММЫ ИЗ ВНУТРЕННЕГО ПРЕДСТАВЛЕНИЯ СИСТЕМЫ КОМПИЛЯТОРОВ GCC Выполнила: студентка 527 группы Алексашина Татьяна Михайловна.
Транспортные сети ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекция 15 Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ,
Информационные технологии Выбор вариантов 2 1.Выполнение последовательности операторов. 2.Выполнение определенной последовательности операторов.
Остовные деревья Лекция 4. Задача «Минимальное остовное дерево» Дано: Граф G, веса c: E(G) R. Найти остовное дерево в G наименьшего веса или определить,
Алгоритмическая структура «Ветвление» Тема урока.
Алгоритмы сканирования и обхода Лекция 3. Алгоритм сканирования графа Input: Орграф (граф) G и вершина s. Output: Множество R вершин, достижимых из s,
Анализ тестового покрытия компиляторов Выполнила: Байцерова Ю.С., 545 Гр. Научный руководитель: ст. преп. Вояковская Н. Н. Рецензент: ст. преп. Луцив Д.В.
Оптимизирующий компилятор. Основные характеристики приложения, влияющие на его производительность: Эффективность вычислений. Эффективность работы с памятью.
Модуль 2. Математичні основи криптографії 1. Лекция 3 Хэш-функции и аутентификация сообщений. Часть 1 1. Хэш-функции. Общие понятия. 2. Хэш-функции основных.
Двумерные массивы. Задачи обработки двумерных массивов.
ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная.
Лекция 2Лекция 2Структура программы Директивы препроцессора main () { Описания переменных Операторы }
Двусвязность Лекция 14. Связность компонент Граф G называется k-связным (k 1), если не существует набора из k-1 или меньшего числа узлов V` V, такого,
Оптимизирующая компиляция. Производительность Параллелизм на уровне операций (ILP) – параллельное исполнение команд в процессоре Параллелизм на уровне.
Лекция 9 Отношения, графы Определения. Определение. Пусть а и b объекты. Через (а, b) обозначим упорядоченную пару, состоящую из объектов а и b, взятых.
Транксрипт:

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

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

ядро компилятора Структура компилятора Компилятор - переводит исходный код программы (написанные на языке высокого уровня) в эквивалентный код на языке целевой платформы Compiler structure.c.cpp.f77....c.cpp.F... High-Level IR Low-Level IR Low-Level IR Low-Level IR asm.o.obj.out.exe Препроцессор 2.2.Front-End 3.3.Оптимизации 4.4.Кодогенератор 5.5.Ассемблер 6.6.Линкер

1.int func( int a, int b) 2.{ 3.int res = 0; 4.int c = 10; 5.int d = 20; 6.int i, j, k = 0; 7.for ( i = 0; i < 100; i++ ) 8.{ 9.for ( j = 0; j < 100; j++ ) 10.{ 11.if ( i + j < a + b ) 12.{ 13.res += a + b + i; 14.} else 15.{ 16.res += c + d + j; 17.} 18.res += b + i; 19.} 20.k++; 21.} 22.return res; 23.} Пример (исходый код программы на С)

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 > D.1552 // 56. RETURN D.1552 // Линейная последовательность операций

Граф потока управления

Граф потока управления с промежуточным представлением

Обход (нумерация) o Обход в глубину (depth first) 1. для каждого преемника { 2. устанавливаем номер обходим рекурсивно преемника } o Обход в ширину (reverse post order) 1. для каждого преемника { 2. обходим рекурсивно преемника } 3. устанавливаем номер -- Маркирование Клонирование Построение дерева доминаторов/постдоминаторов Построение дерева циклов Действия на графе потока управления

Обязательное предшествование (доминирование)

Узел d доминирует/постдоминирует узел n если любой путь от стартового/стопового узла к n проходит через d Алгоритмы построения дерева доминаторов/постдоминаторов o Простейший алгоритм O(N*N) o 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=5y2=z+2 y3=phi(y1,y2) x=y3

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

Построение phi-функций o Для каждой переменной определяем узлы cfg, в которых она инициализируется o Запускаем алгоритм поиска итерационного фронта доминирования (сложность O(|N|*|DF|)*B/size(word)) N – количество узлов в графе потока управления DF – итерационный фронт доминирования для одного узла (в среднем 1-2 на задачах) B – количество переменных size(word) – размер слова в битовом векторе o По результатам работы алгоритма строим phi-функции Линковка записей и чтений Построение SSA/Def-Use графа

CFG CFG+DOM Dominance Frontier Фронт доминирования START STOP d START J-дуги дуги дерева доминаторов b START STOP

Хорошо зарекомендовавшая себя техника потокового анализа. Анализ присваивает одинаковые номера операциям, вырабатывающие одинаковые значения. Номера называются классами эквивалентности. Алгоритмическая сложность O(N * D * Argmax) o N количество операций o D глубина дерева циклов o 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.int func( int a, int b) 2.{ 3.int res = 0; 4.int c = 10; 5.int d = 20; 6.int i, j, k = 0; 7.for ( i = 0; i < 100; i++ ) 8.{ 9.for ( j = 0; j < 100; j++ ) 10.{ 11.if ( i + j < a + b ) 12.{ 13.res += a + b + i; 14.} else 15.{ 16.res += c + d + j; 17.} 18.res += b + i; 19.} 20.k++; 21.} 22.return res; 23.} Исходый код программы

16 (с + d) подстановка констант 11,13 (a+b) сбор общих подвыражений 13,18 (b+i) удаление частично избыточных вычислений 20 (k++) удаление избыточных вычислений 11 (a+b) вынос инвариантных вычислений из цикла Примеры оптимизаций

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