A practical framework for demand-driven interprocedural data flow analysis. TOPLAS

The high cost and growing importance of interprocedural data flow analysis have led to an in-creased interest in demand-driven algorithms. In this article, we present a general framework for developing demand-driven interprocedural data flow analyzers and report our experience in evaluating the performance of this approach. A demand for data flow information is modeled as a set of queries. The framework includes a generic demand-driven algorithm that determines the response to a query by iteratively applying a system of query propagation rules. The propaga-tion rules yield precise responses for the class of distributive nite data flow problems. We also describe a two-phase framework variation to accurately handle nondistributive problems. A perfor-mance evaluation of our demand-driven approach is presented for two data flow problems, namely, reaching-de nitions and copy constant propagation. Our experiments show that demand-driven analysis performs well in practice, reducing both time and space requirements when compared with exhaustive analysis