Abstract
A number of program-analysis problems can be tackled by transforming them into certain kinds of graph-reachability problems in labeled directed graphs. The edge labels can be used to filter out paths that are not interest: a path P from vertex s to vertex t only counts as a“valid connection” between s and t if the word spelled out by P is in a certain language. Often the languages used for such filtering purposes are languages of matching parantheses. In some cases, the matched-parenthesis condition is used to filter out paths with mismatched calls and returns. This leads to so-called “context-sensitive” program analyses, such as context-sensitive interprocedural slicing and context-sensitive interprocedural dataflow analysis. In other cases, the matched-parenthesis condition is used to capture a graph-theoretic analog of McCarthy's rules: “car (cons(x,y)) = x” and “cdr(cons(x,y)) =y”. That is, in the code fragment
c = cons(a,b); d = car(c);
the fact that there is a “structure-transmitted data-dependence” from a to d, but not from b to d, is captured in a graph by (1) using a vertex for each variable, (2)an edge from vertex i to vertex j when i is used on the right-hand side of an assignment to j, (3) parentheses that match as the labels on the edges that run from a to c and c to d, and (4) parentheses that do not match as the labels on the edges that run from a to c and c to d. However, structure-transmitted data-dependence analysis is context-insensitive, because there are no constraints that filter out paths with mismatched calls and returns. Thus, a natural question is whether these two kinds of uses of parentheses can be combined to create a context-sensitive analysis for structure-transmitted data-dependences. This article answers the question in the negative: in general, the problem of context sensitive, structure-transmitted data-dependence analysis is undecidable. The results imply that in general, both context-sensitive set-based analysis and ∞-CFA (when data constructors and selectors and selectors are taken into account) are also undecidable.
- AIKEN, A. AND MURPHY, B.R. 1991a. Implementing regular tree expressions. In Proceedings of the 5th ACM Conference on Functional Programming and Computer Architecture. ACM, 427-447. Google Scholar
- AIKEN, A. AND MURPHY, B.R. 1991b. Static type inference in a dynamically typed language. In Proceedings of the 18th ACM Symposium on the Principles of Programming Languages. ACM, 279-290. Google Scholar
- AIKEN, A. AND WIMMERS, E. L. 1993. Type inclusion constraints and type inference. In Proceedings of the 6th Conference on Functional Programming and Computer Architecture. 31-41. Google Scholar
- CALLAHAN, D. 1988. The program summary graph and flow-sensitive interprocedural data flow analysis. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 47-56. Google Scholar
- COOPER, K. D. AND KENNEDY, K. 1988. Interprocedural side-effect analysis in linear time. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 57-66. Google Scholar
- COOPER, K. D. AND KENNEDY, K. 1989. Fast interprocedural alias analysis. In Proceedings of the 16th ACM Symposium on the Principles of Programming Languages. ACM, 49-59. Google Scholar
- EMAMI, M., GHIYA, R., AND HENDREN, L.J. 1994. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 242-256. Google Scholar
- HARRISON, M.A. 1978. Introduction to Formal Language Theory. Addison-Wesley, Reading, MA. Google Scholar
- HECHT, M.S. 1977. Flow Analysis of Computer Programs. North-Holland, New York. Google Scholar
- HEINTZE, N. 1993. Set-based analysis of ML programs. Tech. Rep. CMU-CS-93-193. School of Computer Science, Carnegie-Mellon Univ., Pittsburgh, PA. Google Scholar
- HEINTZE, N. AND JAFFAR, J. 1991. A decision procedure for a class of set constraints. Tech. Rep. CMU-CS-91-110. School of Computer Science, Carnegie-Mellon Univ., Pittsburgh, PA.Google Scholar
- HEINTZE, N. AND MCALLESTER, D. 1997. Linear-time subtransitive control flow analysis. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 261-272. Google Scholar
- HOPCROFT, J. E. AND ULLMAN, J.D. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA. Google Scholar
- HORWITZ, S., REPS, T., AND BINKLEY, D. 1990. Interprocedural slicing using dependence graphs. ACM Trans. Program. Lang. Syst. 12, 1 (Jan.), 22-60. Google Scholar
- HORWITZ, S., REPS, T., AND SAGIV, M. 1995. Demand interprocedural dataflow analysis. In Proceedings of the 3rd ACM SIGSOFT Symposium on the Foundations of Software Engineering. ACM, 104-115. Google Scholar
- JAGANNATHAN, S. AND WEEKS, S. 1995. A unified treatment of flow analysis in higher-order languages. In Proceedings of the 22nd ACM Symposium on the Principles of Programming Languages. ACM, 393-406. Google Scholar
- JONES, N. D. AND MUCHNICK, S. S. 1981. Flow analysis and optimization of Lisp-like structures. In Prograamm Flow Analysis: Theory and Applications, S. S. Muchnick and N. D. Jones, Eds. Prentice-Hall, 102-131.Google Scholar
- KHEDKER, U. P. AND DHAMDHERE, D.M. 1994. A generalized theory of bit vector data flow analysis. ACM Trans. Program. Lang. Syst. 16, 5 (Sept.), 1472-1511. Google Scholar
- Kou, L.T. 1977. On live-dead analysis for global data flow problems. J. ACM 24, 3 (July), 473-483. Google Scholar
- KUCK, D.J. 1978. The Structure of Computers and Computations. Vol. 1. John Wiley and Sons. Google Scholar
- KUCK, D. J., KUHN, R. H., LEASURE, B., PADUA, D. A., AND WOLFE, M. 1981. Dependence graphs and compiler optimizations. In Proceedings of the 8th ACM Symposium on the Principles of Programming Languages. ACM, 207-218. Google Scholar
- LEWIS, H. R. AND PAPADIMITRIOU, C. H. 1981. Elements of the Theory of Computation. Prentice-Hall. Google Scholar
- MCCARTHY, J. 1963. A basis for a mathematical theory of computation. In Computer Programming and Formal Systems. North-Holland, 33-70.Google Scholar
- MELSKI, D. AND REPS. 2000. Interconvertibility of a class of set constraints and context-free language reachability. Theor. Comput. Sci. 248, 1-2. To be published. Google Scholar
- NIELSON, F. AND NIELSON, H.R. 1997. Infinitary control flow analysis: A collecting semantics for closure analysis. In Proceedings of the 24th ACM Symposium on the Principles of Programming Languages. ACM, 332-345. Google Scholar
- RAMALINGAM, G. 1999. Context-sensitive synchronization-sensitive analysis is undecidable. Res. Rep. TC 21493. IBM T. J. Watson Research Center, Yorktown Heights, NY.Google Scholar
- REPS, T. 1995. Shape analysis as a generalized path problem. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM '95). ACM, 1-11. Google Scholar
- REPS, T. 1996. On the sequential nature of interprocedural program-analysis problems. Acta Inf. 33, 739-757.Google Scholar
- REPS, T. 1998. Program analysis via graph-reachability. Inf. Softw. Tech. 40, 11-12, 701- 726.Google Scholar
- REPS, T., HORWITZ, S., AND SAGIV, M. 1995. Precise interprocedural dataflow analysis via graph-reachability. In Proceedings of the 22nd ACM Symposium on the Principles of Programming Languages. ACM, 49-61. Google Scholar
- REPS, T., HORWITZ, S., SAGIV, M., AND ROSAY, G. 1994. Speeding up slicing. In Proceedings of the 2nd ACM SIGSOFT Symposium on the Foundations of Software Engineering. ACM, 11-20. Google Scholar
- REYNOLDS, J. C. 1968. Automatic computation of data set definitions. In Information Processing 68: Proceedings of the IFIP Congress 68. North-Holland, 456-461.Google Scholar
- SAGIV, M., REPS, T., AND HORWITZ, S. 1996. Precise interprocedural dataflow analysis with applications to constant propagation. Theor. Comput. Sci. 167, 131-170. Google Scholar
- SHARIR, M. AND PNUELI, A. 1981. Two approaches to interprocedural dataflow analysis. In Program Flow Analysis: Theory and Applications, S. S. Muchnick and N. D. Jones, Eds. Prentice-Hall.Google Scholar
- SHIVERS, O. 1988. Control flow analysis in Scheme. In Proceedings of the ACM SIGPLAN 1988 Conference on Programming Languages, Design and Implementation. ACM, 164-174. Google Scholar
- WILSON, R. P. AND LAM, M. S. 1995. Efficient context-sensitive pointer analysis for C programs. In Proceedings of the ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation. ACM, 1-12. Google Scholar
- YANNAKAKIS, M. 1990. Graph-theoretic methods in database theory. In Proceedings of the 9th ACM Symposium on the Principles of Database Systems. ACM, 230-242. Google Scholar
Index Terms
- Undecidability of context-sensitive data-dependence analysis
Recommendations
Context-, flow-, and field-sensitive data-flow analysis using synchronized Pushdown systems
Precise static analyses are context-, field- and flow-sensitive. Context- and field-sensitivity are both expressible as context-free language (CFL) reachability problems. Solving both CFL problems along the same data-flow path is undecidable, which is ...
Pushdown control-flow analysis for free
POPL '16Traditional control-flow analysis (CFA) for higher-order languages introduces spurious connections between callers and callees, and different invocations of a function may pollute each other's return flows. Recently, three distinct approaches have been ...
Context-sensitive data-dependence analysis via linear conjunctive language reachability
POPL '17Many program analysis problems can be formulated as graph reachability problems. In the literature, context-free language (CFL) reachability has been the most popular formulation and can be computed in subcubic time. The context-sensitive data-...
Comments