The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2013-04-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/214 |
| _version_ | 1797877920463585280 |
|---|---|
| author | V. A. Bitner N. V. Zaborovsky |
| author_facet | V. A. Bitner N. V. Zaborovsky |
| author_sort | V. A. Bitner |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T02:25:35Z |
| format | Article |
| id | doaj.art-046db7a79e3343518889858f995e9fe4 |
| institution | Directory Open Access Journal |
| issn | 1818-1015 2313-5417 |
| language | English |
| last_indexed | 2024-04-10T02:25:35Z |
| publishDate | 2013-04-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj.art-046db7a79e3343518889858f995e9fe42023-03-13T08:07:31ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172013-04-0120216617710.18255/1818-1015-2013-2-166-177208The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of AlgorithmsV. A. Bitner0N. V. Zaborovsky1Московский физико-технический институт (государственный университет); Научно-технический центр ИБММосковский физико-технический институт (государственный университет); ООО «Параллелз»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.https://www.mais-journal.ru/jour/article/view/214состояние гонкистатический анализмногопоточные алгоритмыssaоптимизирующий компилятор |
| spellingShingle | V. A. Bitner N. V. Zaborovsky The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms Моделирование и анализ информационных систем состояние гонки статический анализ многопоточные алгоритмы ssa оптимизирующий компилятор |
| title | The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms |
| title_full | The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms |
| title_fullStr | The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms |
| title_full_unstemmed | The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms |
| title_short | The Construction of an Universal Linearized Control Flow Graph for Static Code Analysis of Algorithms |
| title_sort | construction of an universal linearized control flow graph for static code analysis of algorithms |
| topic | состояние гонки статический анализ многопоточные алгоритмы ssa оптимизирующий компилятор |
| url | https://www.mais-journal.ru/jour/article/view/214 |
| work_keys_str_mv | AT vabitner theconstructionofanuniversallinearizedcontrolflowgraphforstaticcodeanalysisofalgorithms AT nvzaborovsky theconstructionofanuniversallinearizedcontrolflowgraphforstaticcodeanalysisofalgorithms AT vabitner constructionofanuniversallinearizedcontrolflowgraphforstaticcodeanalysisofalgorithms AT nvzaborovsky constructionofanuniversallinearizedcontrolflowgraphforstaticcodeanalysisofalgorithms |