Geodesic
The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms
Modelirovanie i analiz informacionnyh sistem, Tome 20 (2013) no. 2, pp. 166-177.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 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.
Mots-clés : race condition, SSA
Keywords: static analysis, multithreaded algorithms, optimizing compiler. 
@article{MAIS_2013_20_2_a12,
     author = {V. A. Bitner and N. V. Zaborovsky},
     title = {The {Construction} of an {Universal} {Linearized} {Control} {Flow} {Graph} for {Static} {Code} {Analysis} of {Algorithms}},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {166--177},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2013_20_2_a12/}
}
TY  - JOUR
AU  - V. A. Bitner
AU  - N. V. Zaborovsky
TI  - The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2013
SP  - 166
EP  - 177
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2013_20_2_a12/
LA  - ru
ID  - MAIS_2013_20_2_a12
ER  - 
%0 Journal Article
%A V. A. Bitner
%A N. V. Zaborovsky
%T The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms
%J Modelirovanie i analiz informacionnyh sistem
%D 2013
%P 166-177
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2013_20_2_a12/
%G ru
%F MAIS_2013_20_2_a12
V. A. Bitner; N. V. Zaborovsky. The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms. Modelirovanie i analiz informacionnyh sistem, Tome 20 (2013) no. 2, pp. 166-177. http://geodesic.mathdoc.fr/item/MAIS_2013_20_2_a12/

[1] A. Yu. Drozdov, Komponentny podkhod k postroeniyu optimiziruyushchikh kompilyatorov, avtoref. dis. ... d-ra tekhn. nauk: 05.13.11, M., 2010, 50 pp.

[2] Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, 1986

[3] N. V. Zaborovsky, Raschetnaya model nakhozhdeniya sostoyany gonok v mnogopotochnykh algoritmakh, dis. ... kand. fiz.-mat. nauk: 05.13.18, M., 2011, 104 pp.

[4] A. Yu. Drozdov, S. V. Novikov, V. V. Shilov, “Effektivny algoritm preobrazovaniya potoka upravleniya v potok dannykh”, Prilozhenie k zhurnalu “Informatsionnye tekhnologii”, 2005, no. 2, 24–31

[5] LLVM API Documentation, http://llvm.org/docs/doxygen/html/IfConversion_8cpp.html

[6] A. Yu. Drozdov, S. V. Novikov, “Issledovanie metodov preobrazovaniya programmy v predikatnuyu formu dlya arkhitektur s yavno vyrazhennoy parallelnostyu”, Kompyutery v uchebnom protsesse, 2005, no. 5 | Zbl

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

[8] D. F. Bacon, S. L. Graham, O. J. Sharp, “Compiler transformations for high performance computing”, ACM Computing Surveys, 26:4 (1994), 345–420 | DOI

[9] LLVM’s Analysis and Transform Passes, http://llvm.org/docs/Passes.html

[10] A. Yu. Drozdov, A. M. Stepanenkov, “Metody kombinirovaniya algoritmov analiza i optimizatsy v sovremennykh optimiziruyushchikh kompilyatorakh”, Kompyutery v uchebnom protsesse, 2004, no. 11, 3–12

[11] O. V. Medvedev, “Linearizatsiya grafa potoka upravleniya s uchetom rezultatov profilirovaniya”, Sistemnoe programmirovanie, 2:1 (2006), 25–47

[12] M. Yu. Kudrin, A. S. Prokopenko, A. G. Tormasov, “Metod nakhozhdeniya sostoyany gonki v potokakh, rabotayushchikh na razdelyaemoy pamyati”, Sbornik nauchnykh trudov MFTI, 1, no. 4, MFTI, M., 2009, 181–201