Реализация межпроцедурного анализа указателей в рамках LLVM на основе линейной алгебры

Задача межпроцедурного анализа алиасов (анализа указателей) является одной из ключевых в компиляторных инфраструктурах. В частности, в рамках LLVM реализован ряд различных проходов (passes), решающих эту задачу. Не так давно Илья Муравьёв в своей работе Оптимизация алгоритма контекстно-свободной достижимости, основанного на операциях линейной алгебры предложил высокопроизводительный алгоритм решения этой задачи. В настоящее время ведётся работа по его реализации в рамках библиотеки LAGraph Предлагается на основе данной реализации реализовать свой проход для LLVM. Кроме этого, нужно будет провести сравнение с уже имеющимися аналогами в рамках LLVM.

Требования к студенту
  • Хорошие знания языка программирования С++ и соответствующего инструментария разработчика: сборка, отладка, профилирование, проверка стиля кодирования и качества кода.
  • Хорошие знания языка программирования С и соответствующего инструментария разработчика: сборка, отладка, профилирование, проверка стиля кодирования и качества кода.
  • Знания основ статического анализа кода: внутрипроцедурный анализ, межпроцедурный анализ, классические задачи и алгоритмы их решения (анализ указателей, другие анализы потока данных).
  • Знания основ теории графов: ориентированные помеченные графы, представление в виде матрицы смежности, алгоритмы проверки достижимости и поиска путей, алгоритмы обхода графа.
  • Знания основы теории формальных языков: контекстно-свободные грамматики, понятие выводимости в грамматике, нормальные формы грамматик (нормальная форма Хомского, BNF, EBNF).
  • Хорошее знакомство с инфраструктурой LLVM: IR, проходы, представление об архитектуре.
Уровень

3 курс , Бакалаврская ВКР

Руководитель

Григорьев Семен Вячеславович

Консультант

Grigorev Semyon

Источник

Кафедра системного программирования СПбГУ