A Generic Worklist Algorithm for Graph Reachability Problems in Program Analysis

Many program analyses involve, or can be expressed in terms of, a graph reachability problem. We present a generic worklist-style algorithm capable of expressing and solving the graph reachability components of many such analyses. We compare our framework with the language reachability framework proposed by Thomas Reps, and show that some problems are expressible in both frameworks, and some problems can be expressed in only one of the frameworks. Our two main case studies are Choi et al’s escape analysis and Bacon & Sweeney’s rapid type analysis (RTA). The reachability problems in these analyses can be directly expressed in the framework of our algorithm, but not in the language reachability framework. We discuss why this is the case, but important future work remains to formally characterize the kinds of problems that are amenable to our approach. The paper also summarizes our experimental work with an implementation of RTA based on our generic algorithm.