Построение универсального линеаризованного графа потока управления для использования в статическом анализе кода алгоритмов

В работе рассматривается вариант построения универсального линеаризованного графа потока управления, архитектурно-независимого и пригодного для описания программы любого языка программирования высокого уровня. Практическая польза данного графа заключается в возможности быстрого и оптимального поиска уникальных путей исполнения, что может быть особенно ценно в методах статического анализа кода алгоритмов с целью поиска в них состояния гонки («race condition»). В качестве технического средства для построения линеаризованного графа управления используется оптимизирующий компилятор CLANG&LLVM. В работе проводится анализ попроцедурных оптимизаций компилятора LLVM, трансформация промежуточного представления которых приводит как к сокращению количества инструкций условного и безусловного перехода в коде, так и к удалению или упрощению целых циклов и условных конструкций. Результат анализа, приведенный в работе, позволил выявить наиболее эффективную линейку оптимизаций компилятора LLVM, которая приводит к существенной линеаризации графа потока управления, что было продемонстрировано на примере кода взаимоисключающего алгоритма Петерсона для 2 потоков.

1. Дроздов А.Ю. Компонентный подход к построению оптимизирующих компиляторов: автореф. дис. ... д-ра техн. наук: 05.13.11. М., 2010. 50 с. (Drozdov A.Yu. Komponentny podkhod k postroeniyu optimiziruyushchikh kompilyatorov: avtoref. dis. ... d-ra tekhn. nauk: 05.13.11. Moskva, 2010. 50 s. [in Russian]).

2. Ахо А.В., Сети Р., Ульман Д.Д. Компиляторы: принципы, технологии и инструменты. М.: Вильямс, 2003. 768 c. (English transl.: Compilers: Principles, Techniques, and Tools / Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, 1986.)

3. Заборовский Н.В. Расчетная модель нахождения состояний гонок в многопоточных алгоритмах: дис. ... канд. физ.-мат. наук: 05.13.18. М., 2011. 104 с. (Zaborovsky N.V. Raschetnaya model nakhozhdeniya sostoyany gonok v mnogopotochnykh algoritmakh: dis. ... kand. fiz.-mat. nauk: 05.13.18. Moskva, 2011. 104 s. [in Russian]).

4. Дроздов А.Ю., Новиков С.В., Шилов В.В. Эффективный алгоритм преобразования потока управления в поток данных // Приложение к журналу “Информационные технологии”. 2005. № 2. С. 24–31 (Drozdov A.Yu., Novikov S.V., Shilov V.V. Effektivny algoritm preobrazovaniya potoka upravleniya v potok dannykh // Prilozhenie k zhurnalu "Informatsionnye tekhnologii". 2005. № 2. S. 24–31 [in Russian]).

5. LLVM API Documentation [Электронный ресурс]. Режим дост.: http://llvm.org/docs/doxygen/html/IfConversion_8cpp.html

6. Дроздов А.Ю., Новиков С.В. Исследование методов преобразования программы в предикатную форму для архитектур с явно выраженной параллельностью // Компьютеры в учебном процессе. 2005. № 5 (Drozdov A.Yu., Novikov SV. Issledovanie metodov preobrazovaniya programmy v predikatnuyu formu dlya arkhitektur s yavno vyrazhennoy parallelnostyu // Kompyutery v uchebnom protsesse. 2005. № 5 [in Russian]).

7. Muchnick Steven S. Advanced Compiler Design and Implementation, San Francisco: Morgan Kauffman, 1997.

8. Bacon D.F., Graham S.L., Sharp O.J. Compiler transformations for high performance computing // ACM Computing Surveys. 1994. 26(4). P. 345–420.

9. LLVM’s Analysis and Transform Passes [Электронный ресурс]. Режим дост.: http://llvm.org/docs/Passes.html

10. Дроздов А.Ю., Степаненков А.М. Методы комбинирования алгоритмов анализа и оптимизаций в современных оптимизирующих компиляторах // Компьютеры в учебном процессе. 2004. №11. С. 3–12 (Drozdov A.Yu., Stepanenkov A.M. Metody kombinirovaniya algoritmov analiza i optimizatsy v sovremennykh optimiziruyushchikh kompilyatorakh // Kompyutery v uchebnom protsesse. 2004. №11. S. 3–12 [in Russian]).

11. Медведев О.В. Линеаризация графа потока управления c учётом результатов профилирования // Системное программирование. 2006. Т. 2, №1. С. 25–47 (Medvedev O.V.

12. Linearizatsiya grafa potoka upravleniya s uchetom rezultatov profilirovaniya // Sistemnoe programmirovanie. 2006. T. 2, № 1. S. 25–47 [in Russian]).

13. Кудрин М.Ю., Прокопенко А.С., Тормасов А.Г. Метод нахождения состояний гонки в потоках, работающих на разделяемой памяти // Сборник научных трудов МФТИ. М.: МФТИ, 2009. № 4. Том 1. С. 181–201 (Kudrin M.Yu., Prokopenko A.S., Tormasov A.G. Metod nakhozhdeniya sostoyany gonki v potokakh, rabotayushchikh na razdelyaemoy pamyati // Sbornik nauchnykh trudov MFTI. Moskva: MFTI, 2009. № 4. Tom 1. S. 181–201 [in Russian]).