ML-Driven Prediction of Optimal Control Flow Graph Traversal Algorithm in Modern Applications

Abstract

Control flow graph models program execution paths and is essential for program analysis and compiler optimizations. Compilers traverse thousands of graphs during compilation, thus, efficient control flow graph traversal is crucial. Prior work shows that breadth-first and depth-first search algorithms can perform differently depending on the graph structure, but the impact of graph features on the choice of the traversal algorithm remained underexplored. In this paper, we construct a dataset of over 200,000 control flow graphs extracted from modern JVM-based applications and train an ensemble-based machine learning model to predict the optimal graph traversal algorithm using only a set of lightweight graph features. Our model identifies the key features that drive accurate predictions, and we demonstrate that these informative features can be efficiently extracted during control flow graph construction.