×

You are using an outdated browser Internet Explorer. It does not support some functions of the site.

Recommend that you install one of the following browsers: Firefox, Opera or Chrome.

Contacts:

+7 961 270-60-01
ivdon3@bk.ru

Evaluation of the complexity of algorithms for building a dominator tree in the context of the implementation of algorithms for data flow analysis in the implementation of the frontend compiler of the Solidity programming language

Abstract

Evaluation of the complexity of algorithms for building a dominator tree in the context of the implementation of algorithms for data flow analysis in the implementation of the frontend compiler of the Solidity programming language

Stolyarov V.R., Larin S.V., Skobel'tsyn S.A.

Incoming article date: 06.09.2024

This article discusses two of the most popular algorithms for constructing dominator trees in the context of static code analysis in the Solidity programming language. Both algorithms, the Cooper, Harvey, Kennedy iterative algorithm and the Lengauer-Tarjan algorithm, are considered effective and widely used in practice. The article compares these algorithms, evaluates their complexity, and selects the most preferable option in the context of Solidity. Criteria such as execution time and memory usage were used for comparison. The Cooper, Harvey, Kennedy iterative algorithm showed higher performance when working with small projects, while the Lengauer-Tarjan algorithm performed better when analyzing larger projects. However, overall, the Cooper, Harvey, Kennedy iterative algorithm was found to be more preferable in the context of Solidity as it showed higher efficiency and accuracy when analyzing smart contracts in this programming language. In conclusion, this article may be useful for developers and researchers who are involved in static code analysis in the Solidity language, and who can use the results and conclusions of this study in their work.

Keywords: dominator tree, Solidity, algorithm comparison