Efficient control-flow graph traversal

In the process of program translation, compilers traverse a large number of control flow graphs, and therefore the speed of individual traversals can significantly impact overall compilation time. While standard algorithms for graph traversal such as Breadth-First Search (BFS) and Depth-First Search (DFS) operate in linear time and space complexity concerning the number of nodes and edges in the graph, their execution time and memory usage vary depending on the shape of the graph and the data structure used in the algorithm implementation. We analyze the time and space efficiency of executing control flow graph traversals obtained by compiling Java and Scala programs using the Graal compiler. The results analysis shows that the breadth-first traversal of control flow graphs is up to 1.6 times faster than depth-first traversal and incurs lower memory overhead across all benchmark programs. We also demonstrate that the choice of data structure used in the algorithm implementation affects its speed, with a doubly linked list proving to be the most efficient across all benchmark programs.