Results from a large-scale study of performance optimization techniques for source code analyses based on graph reachability algorithms

Internally, many source code analysis tools make use of graphs. For example, one of the oldest and most widely used internal graphs is the control-flow graph developed for use within a compiler. Work on compilation has also led to the development of the call graph, the procedure dependence graph (PDG), and the static-single assignment (SSA) graph. Compilers are not the only source-code analysis tools to use internal graphs. A variety of software engineering tools incorporate a variety of different graphs. A study of techniques that improve graph-based program analysis is presented. Several different techniques are considered, including forming strongly-connected components, topological sorting, and removing transitive edges. Graph reachability, a pervasive graph analysis operation, is used as a representative graph analysis operation in the study. Data collected from a test bed of just over 1000000 lines of code is presented. This data illustrates the impact on computation time of the improvement techniques. Overall, the combination of all techniques produces a 71% reduction in run-time (and 64% reduction in memory usage). In other words, they increase the size of the problem that can be effectively handled by factor of over three times.