Sixth European Conference on Software Maintenance and Reengineering A Generic Worklist Algorithm for Graph Reachability Problems in Program Analysis Budapest, Hungary March 11-March 13 ISBN: 0-7695-1438-3
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 expressable 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.
Citation:
Derek Rayside, Kostas Kontogiannis, "A Generic Worklist Algorithm for Graph Reachability Problems in Program Analysis," csmr, pp.0067, Sixth European Conference on Software Maintenance and Reengineering, 2002 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||