Санкт-Петербургский Государственный Университет Математико-Механический факультет Кафедра системного программирования Применение диаграмм двоичных решений для задачи анализа потока данных Дипломная работа студента 544 группы Ловцюса Андрея Вячеславовича Научный руководитель – А.В.Друнин Рецензент – к.ф-м.н Д.Ю.Булычев

Введение Система реинжиниринга «Modernization Workbench» Классическая реализация анализа достигающих определений Использование битовых векторов Вычисление решения итерированием по узлам CFG Анализ больших программ, написанных на языке COBOL Большое время работы анализа достигающих определений Излишнее расходование памяти на хранение информации о потоке данных

Цель работы Эффективная реализация анализа достигающих определений Использование диаграмм двоичных решений (Binary Decision Diagrams, BDD) Сокращение размеров BDD, используемых в решении

Алгоритм (вариант 1)

Алгоритм (вариант 2)

Эффективность BDD Порядок переменных BDD Нумерация присваиваний Сокращение представления Kill множеств Сокращение представления Gen множеств Нумерация вершин графа

Производительность

Результаты Реализованы два способа решения задачи достигающих определений с использованием BDD Опробованы различные способы минимизации размеров диаграмм Реализованные методы оказались эффективнее классического по потреблению памяти Только один метод эффективен по времени