Abstract
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.
This work was supported in part by a David and Lucile Packard Fellowship for Science and Engineering, by the National Science Foundation under grants CCR-8958530 and CCR-9100424, by the Defense Advanced Research Projects Agency under ARPA Order No. 8856 (monitored by the Office of Naval Research under contract N00014-92-J-1937), by the Air Force Office of Scientific Research under grant AFOSR-91-0308, and by a grant from Xerox Corporate Research. Part of this work was done while the authors were visiting the University of Copenhagen.
On leave from IBM Scientific Center, Haifa, Israel.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
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.
D. Callahan, K.D. Cooper, K. Kennedy, and L. Torczon. Interprocedural constant propagation. In SIGPLAN Symposium on Compiler Construction, pages 152–161, 1986.
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.
C.N. Fischer and R.J. LeBlanc. Crafting a Compiler. Benjamin/Cummings Publishing Company, Inc., Menlo Park, CA, 1988.
D. Grove and L. Torczon. A study of jump function implementations. In SIGPLAN Conference on Programming Languages Design and Implementation, pages 90–99, 1993.
S. Horwitz, T. Reps, and M. Sagiv. Demand interprocedural dataflow analysis. Unpublished manuscript, 1995.
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.
M. Karr. Affine relationship among variables of a program. Acta Inf., 6:133–151, 1976.
G.A. Kildall. A unified approach to global program optimization. In ACM Symposium on Principles of Programming Languages, pages 194–206, 1973.
J. Knoop and B. Steffen. The interprocedural coincidence theorem. In International Conference on Compiler Construction, pages 125–140, 1992.
W. Landi and B.G. Ryder. Pointer induced aliasing: A problem classification. In ACM Symposium on Principles of Programming Languages, pages 93–103, 1991.
R. Metzger and S. Stroud. Interprocedural constant propagation: An empirical study. ACM Letters on Programming Languages and Systems, 2, 1993.
T. Reps. Solving demand versions of interprocedural analysis problems. In International Conference on Compiler Construction, pages 389–403, 1994.
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.
T. Reps, M. Sagiv, and S. Horwitz. Interprocedural dataflow analysis via graph reachability. Technical Report TR 94-14, Datalogisk Institut, University of Copenhagen, 1994.
B. Steffen and J. Knoop. Finite constants: Characterizations of a new decidable set of constants. Theoretical Computer Science, 80(2):303–318, 1991.
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.
SPEC Component CPU Integer Release 2/1992 (Cint92). Standard Performance Evaluation Corporation (SPEC), Fairfax, VA, 1992.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sagiv, M., Reps, T., Horwitz, S. (1995). Precise interprocedural dataflow analysis with applications to constant propagation. In: Mosses, P.D., Nielsen, M., Schwartzbach, M.I. (eds) TAPSOFT '95: Theory and Practice of Software Development. CAAP 1995. Lecture Notes in Computer Science, vol 915. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-59293-8_226
Download citation
DOI: https://doi.org/10.1007/3-540-59293-8_226
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-59293-8
Online ISBN: 978-3-540-49233-7
eBook Packages: Springer Book Archive