Precise interprocedural dataflow analysis with applications to constant propagation. (English) Zbl 1496.68079
Mosses, Peter D. (ed.) et al., TAPSOFT ’95: Theory and practice of software development. 6th international joint conference CAAP/FASE, Aarhus, Denmark, May 1995. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 915, 651-665 (1995).
Summary: This paper concerns interprocedural dataflow-analysis problems in which the dataflow information at a program point is represented by an environment (i.e., a mapping from symbols to values), and the effect of a program operation is represented by a distributive environment transformer. We present an efficient dynamic-programming algorithm that produces precise solutions.
The method is applied to solve precisely and efficiently two (decidable) variants of the interprocedural constant-propagation problem: copy constant propagation and linear constant propagation. The former interprets program statements of the form \(x :=7\) and \(x :=y\). The latter also interprets statements of the form \(x :=5*y+17\).
For the entire collection see [Zbl 0835.68002].
The method is applied to solve precisely and efficiently two (decidable) variants of the interprocedural constant-propagation problem: copy constant propagation and linear constant propagation. The former interprets program statements of the form \(x :=7\) and \(x :=y\). The latter also interprets statements of the form \(x :=5*y+17\).
For the entire collection see [Zbl 0835.68002].
References:
| [1] | D. Callahan. The program summary graph and flow-sensitive interprocedural data flow analysis. In SIGPLAN Conference on Programming Languages Design and Implementation, pages 47-56, 1988. |
| [2] | D. Callahan, K.D. Cooper, K. Kennedy, and L. Torczon. Interprocedural constant propagation. In SIGPLAN Symposium on Compiler Construction, pages 152-161, 1986. |
| [3] | E. Duesterwald, R. Gupta, and M.L. Soffa. Demand-driven computation of interprocedural data flow. In ACM Symposium on Principles of Programming Languages, pages 37-48, 1995. |
| [4] | C.N. Fischer and R.J. LeBlanc. Crafting a Compiler. Benjamin/Cummings Publishing Company, Inc., Menlo Park, CA, 1988. |
| [5] | D. Grove and L. Torczon. A study of jump function implementations. In SIGPLAN Conference on Programming Languages Design and Implementation, pages 90-99, 1993. |
| [6] | S. Horwitz, T. Reps, and M. Sagiv. Demand interprocedural dataflow analysis. Unpublished manuscript, 1995. |
| [7] | N.D. Jones and A. Mycroft. Data flow analysis of applicative programs using minimal function graphs. In ACM Symposium on Principles of Programming Languages, pages 296-306, 1986. |
| [8] | M. Karr. Affine relationship among variables of a program. Acta Inf., 6:133-151, 1976. · Zbl 0358.68025 |
| [9] | G.A. Kildall. A unified approach to global program optimization. In ACM Symposium on Principles of Programming Languages, pages 194-206, 1973. · Zbl 0309.68020 |
| [10] | J. Knoop and B. Steffen. The interprocedural coincidence theorem. In International Conference on Compiler Construction, pages 125-140, 1992. |
| [11] | W. Landi and B.G. Ryder. Pointer induced aliasing: A problem classification. In ACM Symposium on Principles of Programming Languages, pages 93-103, 1991. |
| [12] | R. Metzger and S. Stroud. Interprocedural constant propagation: An empirical study. ACM Letters on Programming Languages and Systems, 2, 1993. |
| [13] | T. Reps. Solving demand versions of interprocedural analysis problems. In International Conference on Compiler Construction, pages 389-403, 1994. |
| [14] | T. Reps, S. Horwitz, and M. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In ACM Symposium on Principles of Programming Languages, pages 49-61, 1995. |
| [15] | T. Reps, M. Sagiv, and S. Horwitz. Interprocedural dataflow analysis via graph reachability. Technical Report TR 94-14, Datalogisk Institut, University of Copenhagen, 1994. · Zbl 0874.68133 |
| [16] | B. Steffen and J. Knoop. Finite constants: Characterizations of a new decidable set of constants. Theoretical Computer Science, 80(2):303-318, 1991. · Zbl 0745.68040 |
| [17] | M. Sharir and A. Pnueli. Two approaches for interprocedural data flow analysis. In S.S. Muchnick and N.D. Jones, editors, Program Flow Analysis: Theory and Applications, chapter 7, pages 189-234. Prentice-Hall, 1981. |
| [18] | SPEC Component CPU Integer Release 2/1992 (Cint92). Standard Performance Evaluation Corporation (SPEC), Fairfax, VA, 1992. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
