loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Derek Rayside, University of Waterloo
Kostas Kontogiannis, University of Waterloo
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.