Precise interprocedural dataflow analysis via graph reachability Export

@inproceedings{citeulike:778826, abstract = {The paper shows how a large class of interprocedural dataflow-analysis problems can be solved precisely in polynomial time by transforming them into a special kind of graph-reachability problem. The only restrictions are that the set of dataflow facts must be a finite set, and that the dataflow functions must distribute over the confluence operator (either union or intersection). This class of probable problems includes\—but is not limited to\—the classical separable problems (also known as \“gen/kill\” or \“bit-vector\” problems)\— e.g. , reaching definitions, available expressions, and live variables. In addition, the class of problems that our techniques handle includes many non-separable problems, including truly-live variables, copy constant propagation, and possibly-uninitialized variables. Results are reported from a preliminary experimental study of C programs (for the problem of finding possibly-uninitialized variables).}, address = {New York, NY, USA}, author = {Reps, Thomas and Horwitz, Susan and Sagiv, Mooly}, booktitle = {POPL '95: Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages}, citeulike-article-id = {778826}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=199462}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/199448.199462}, doi = {10.1145/199448.199462}, isbn = {0-89791-692-1}, keywords = {dataflow-analysis}, location = {San Francisco, California, United States}, pages = {49--61}, posted-at = {2007-09-19 08:10:41}, priority = {2}, publisher = {ACM}, title = {Precise interprocedural dataflow analysis via graph reachability}, url = {http://dx.doi.org/10.1145/199448.199462}, year = {1995} }

TY - CONF ID - citeulike:778826 L3 - citeulike-article-id:778826 N2 - The paper shows how a large class of interprocedural dataflow-analysis problems can be solved precisely in polynomial time by transforming them into a special kind of graph-reachability problem. The only restrictions are that the set of dataflow facts must be a finite set, and that the dataflow functions must distribute over the confluence operator (either union or intersection). This class of probable problems includes—but is not limited to—the classical separable problems (also known as “gen/kill” or “bit-vector” problems)— e.g. , reaching definitions, available expressions, and live variables. In addition, the class of problems that our techniques handle includes many non-separable problems, including truly-live variables, copy constant propagation, and possibly-uninitialized variables. Results are reported from a preliminary experimental study of C programs (for the problem of finding possibly-uninitialized variables). CY - San Francisco, California, United States SN - 0-89791-692-1 AD - New York, NY, USA EP - 61 TI - Precise interprocedural dataflow analysis via graph reachability PB - ACM T2 - POPL '95: Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages SP - 49 KW - dataflow-analysis AU - Reps, Thomas AU - Horwitz, Susan AU - Sagiv, Mooly PY - 1995/// UR - http://dx.doi.org/10.1145/199448.199462 ER -