аспирант кафедры информатики,
141700, Московская область, г. Долгопрудный, Институтский переулок, 9
аспирант кафедры информатики,
9 Institutskiy lane, Dolgoprudny city, Moscow Region, 141700, Russia
лектор кафедры информатики,
141700, Московская область, г. Долгопрудный, Институтский переулок, 9
лектор кафедры информатики,
9 Institutskiy lane, Dolgoprudny city, Moscow Region, 141700, Russia
В работе рассматривается вариант построения универсального линеаризованного графа потока управления, архитектурно-независимого и пригодного для описания программы любого языка программирования высокого уровня. Практическая польза данного графа заключается в возможности быстрого и оптимального поиска уникальных путей исполнения, что может быть особенно ценно в методах статического анализа кода алгоритмов с целью поиска в них состояния гонки («race condition»). В качестве технического средства для построения линеаризованного графа управления используется оптимизирующий компилятор CLANG&LLVM. В работе проводится анализ попроцедурных оптимизаций компилятора LLVM, трансформация промежуточного представления которых приводит как к сокращению количества инструкций условного и безусловного перехода в коде, так и к удалению или упрощению целых циклов и условных конструкций. Результат анализа, приведенный в работе, позволил выявить наиболее эффективную линейку оптимизаций компилятора LLVM, которая приводит к существенной линеаризации графа потока управления, что было продемонстрировано на примере кода взаимоисключающего алгоритма Петерсона для 2 потоков.
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.
The authors declare that there are no conflicts of interest present.