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
Incoming article date: 06.09.2024This 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