|
Моделирование и анализ информационных систем, 2013, том 20, номер 2, страницы 166–177
(Mi mais306)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Построение универсального линеаризованного графа потока управления для использования в статическом анализе кода алгоритмов
В. А. Битнер, Н. В. Заборовский Московский физико-технический институт (государственный университет), 141700, Московская область, г. Долгопрудный, Институтский переулок, 9
Аннотация:
В работе рассматривается вариант построения универсального линеаризованного графа потока управления, архитектурно-независимого и пригодного для описания программы любого языка программирования высокого уровня. Практическая польза данного графа заключается в возможности быстрого и оптимального поиска уникальных путей исполнения, что может быть особенно ценно в методах статического анализа кода алгоритмов с целью поиска в них состояния гонки («race condition»). В качестве технического средства для построения линеаризованного графа управления используется оптимизирующий компилятор CLANG&LLVM. В работе проводится анализ попроцедурных оптимизаций компилятора LLVM, трансформация промежуточного представления которых приводит как к сокращению количества инструкций условного и безусловного перехода в коде, так и к удалению или упрощению целых циклов и условных конструкций. Результат анализа, приведенный в работе, позволил выявить наиболее эффективную линейку оптимизаций компилятора LLVM, которая приводит к существенной линеаризации графа потока управления, что было продемонстрировано на примере кода взаимоисключающего алгоритма Петерсона для 2 потоков.
Ключевые слова:
состояние гонки, статический анализ, многопоточные алгоритмы, SSA, оптимизирующий компилятор.
Поступила в редакцию: 25.03.2013
Образец цитирования:
В. А. Битнер, Н. В. Заборовский, “Построение универсального линеаризованного графа потока управления для использования в статическом анализе кода алгоритмов”, Модел. и анализ информ. систем, 20:2 (2013), 166–177
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mais306 https://www.mathnet.ru/rus/mais/v20/i2/p166
|
|