Machine Learning-Driven Prediction of Optimal Control Flow Graph Traversal Strategy

Abstract

Control flow graphs model possible program execution paths and thus are essential for static program analysis. Compilers use control flow graphs as a basis for their intermediate representations, allowing them to apply optimizations. As each method is represented by its control flow graph, the number of control flow graphs that a compiler needs to generate and process depends on the program being compiled. For reference, modern programs that run on the JVM consist of hundreds of thousands of methods. Thus, efficient control flow graph traversal is crucial to provide fast compilation. Prior work has shown that breadth-first and depth-first search algorithms yield different results depending on the control flow graph structure; however, the relationship between control flow graph features and the optimal traversal algorithm in terms of traversal speed remains underexplored. In this work, we construct a dataset of over 200, 000 control flow graphs gathered from modern state-of-the-art JVM benchmark suites. Using this dataset, we train a set of ensemble-based machine learning models that predict optimal graph traversal algorithms for a given control flow graph using a set of lightweight graph features. Our models identify the key features that yield accurate predictions and demonstrate that the most informative features can be extracted efficiently during the graph construction process itself.