The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms
https://doi.org/10.18255/1818-1015-2013-2-166-177
Abstract
This paper presents the description of a possible way to build the universal linearized control flow graph which is supposed to be architecture-independent and applicable to the description of any high level language programs. The practical usefulness of the graph considered is the existence of the fast and optimal search of the unique execution paths that is valuable in the methods of static code analysis of algorithms for race condition search. Optimizing compiler CLANG&LLVM is used as a technical tool for building a linearized control flow graph. The analysis of LLVM compiler procedural optimizations is carried out in the article. Transformations of intermediate representation of those optimizations result in reduction of the number of instructions responsible for conditional or unconditional branches in the code as well as the elimination or simplification of the whole loops and conditional constructions. The results of the analysis performed in the paper allowed revealing the most effective optimizations line of the LLVM compiler, which leads to a significant linearization of the control flow graph. That fact was demonstrated by the example code of the Peterson mutual execution algorithm for 2 threads.
About the Authors
V. A. Bitner
MIPT, Informatics Department
Russian Federation
Russian Federation
аспирант кафедры информатики,
9 Institutskiy lane, Dolgoprudny city, Moscow Region, 141700, Russia
N. V. Zaborovsky
MIPT, Informatics Department
Russian Federation
Russian Federation
лектор кафедры информатики,
9 Institutskiy lane, Dolgoprudny city, Moscow Region, 141700, Russia
References
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]).
Review
For citations:
Bitner V.A., Zaborovsky N.V. The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms. Modeling and Analysis of Information Systems. 2013;20(2):166-177. (In Russ.) https://doi.org/10.18255/1818-1015-2013-2-166-177
Views:
1028
Email this article 