RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Model. Anal. Inform. Sist., 2013, Volume 20, Number 2, Pages 166–177 (Mi mais306)  

The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms

V. A. Bitner, N. V. Zaborovsky

MIPT, Informatics Department, 9 Institutskiy lane, Dolgoprudny city, Moscow Region, 141700, Russia

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.

Keywords: race condition, static analysis, multithreaded algorithms, SSA, optimizing compiler.

Full text: PDF file (778 kB)
References: PDF file   HTML file
UDC: 004.451.2
Received: 25.03.2013

Citation: V. A. Bitner, N. V. Zaborovsky, “The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms”, Model. Anal. Inform. Sist., 20:2 (2013), 166–177

Citation in format AMSBIB
\Bibitem{BitZab13}
\by V.~A.~Bitner, N.~V.~Zaborovsky
\paper The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms
\jour Model. Anal. Inform. Sist.
\yr 2013
\vol 20
\issue 2
\pages 166--177
\mathnet{http://mi.mathnet.ru/mais306}


Linking options:
  • http://mi.mathnet.ru/eng/mais306
  • http://mi.mathnet.ru/eng/mais/v20/i2/p166

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Моделирование и анализ информационных систем
    Number of views:
    This page:461
    Full text:193
    References:26

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019