A PRACTICAL FRAMEWORK FOR DEMAND-DRIVEN INTERPROCEDURAL DATA-FLOW ANALYSIS

The high cost and growing importance of interprocedural data Row analy sis have led to an increased interest in demand-driven algorithms. In this article, we present a general framework for developing demand-dri ven interprocedural data flow analyzers and report our experience in e valuating the performance of this approach, A demand for data flow inf ormation is modelled as a set of queries. The framework includes a gen eric demand-driven algorithm that determines the response to a query b y iteratively applying a system of query propagation rules, The propag ation rules yield precise responses for the class of distributive fini te data Row problems, We also describe a two-phase framework variation to accurately handle non-distributive problems. A performance evaluat ion of our demand-driven approach is presented for two data flow probl ems, namely, reaching-definitions and copy constant propagation. Our e xperiments show that demand-driven analysis performs well in practice, reducing both time and space requirements when compared with exhausti ve analysis.