Jeffrey M. Barth
Abstract
A new interprocedural data flow analysis algorithm is presented and analyzed. The algorithm associates with each procedure in a program information about which variables may be modified, which may be used, and which are possibly preserved by a call on the procedure, and all of its subcalls. The algorithm is sufficiently powerful to be used on recursive programs and to deal with the sharing of variables which arises through reference parameters. The algorithm is unique in that it can compute all of this information in a single pass, not requiring a prepass to compute calling relationships or sharing patterns. The algorithm is asymptotically optimal in time complexity. It has been implemented and is practical even on programs which are quite large.
- 1 Allen, F.E. Interprocedural data flow analysis. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 398--402.Google Scholar
- 2 Allen, F.E., and Schwartz, J.T. Determining the data relationships in a collection of procedures (unpublished detailed summary).Google Scholar
- 3 Ammann, U. Compiler for PASCAL 6000--3.4. ETH, Institut fiir Informatik, Zurich, Switzerland, 1974.Google Scholar
- 4 Barth, J.M. An interprocedural data flow analysis algorithm. Conf. Rec. Fourth ACM Symp, Principles of Programming Languages, Los Angeles, Calif., Jan. 1977, pp. 119-13 I. Google ScholarDigital Library
- 5 Barth, J.M. A practical interprocedural data flow analysis algorithm and its applications. Ph.D. Diss., Comptr. Sci. Tech. Rep. No. 770520, U. of California, Berkeley, May 1977. Google ScholarDigital Library
- 6 Graham, S.L., and Wegrnan, M. A fast and usually linear algorithm for global flow analysis. J. ACM 23, I (Jan. 1976), 172-202. Google ScholarDigital Library
- 7 Hecht, M.S., and Shaffer, J.B. Ideas on the design of a "quad improver" for SIMPL-T, Pt. I: Overview and intersegment analysis. Comptr. Sci. Tech, Rcp. TR-405, U. of Maryland, CoUege Park, Md., Aug. 1975. This report is superceded by {8}, but contains some information not in the latter paper.Google Scholar
- 8 Hecht, M.S., and Shaffer, J.B. A modest quad improver for SIMPL-T, Dept. Comptr. Sci., U. of Maryland, CoUegc Park, Md., April 1977.Google Scholar
- 9 Hecht, M.S., and UUman, J.D. A simple algorithm for global flow problems. SIAM J. Comptng. 4, 4 (Dec. 1975), 519-532.Google ScholarCross Ref
- 10 Jensen, K., Wirth, N. PASCAL User Manual and Report. Leciure Notes in Computer Science No. 18, Springer-Verlag, Berlin, 1974. Google ScholarDigital Library
- 11 Lomet, D.B. Data flow analysis in the presence of procedure calls. Res. Rep. RC5728 IBM T.J. Watson Res. Ctr., Yorktown Heights, N.Y., Nov. 1975.Google Scholar
- 12 Nanr, P. Ed. Revised report on the algorithmic language Algol- 60. Comm. ACM 6, 1 (Jan. 1963), 1-17. Google ScholarDigital Library
- 13 Rosen, B.K. Data flow analysis for recursive PL/I programs. Res, Rep. RC5211, IBM T.J. Watson Res. Ctr., Yorktown Heights, N.Y., Jan. 1975. This report is superceded by {16}.Google Scholar
- 14 Rosen, B.K. High level data flow analysis, Pt. 1 (classical structured programming). Res. Rep. RC5598, IBM, T.J. Watson Res. Ctr., Yorktown Heights, N.Y., Aug. 1975.Google Scholar
- 15 Rosen, B.K. High level data flow analysis, Pt. 2 (escapes and jumps). Res. Rep. RC5744, IBM T.J. Watson Res. Ctr., Yorktown Heights, N.Y. Dec. 1975.Google Scholar
- 16 Rosen, B.K. Data flow analysis for procedural languages. T.J. Watson Res. Ctr., Yorktown Heights, N.Y., 1976.Google Scholar
- 17 Spillman, T.C. Exposing side effects in a PL/I optimizing compiler. Proceedings IFIP Conference 1971, North Holland Publishing Company, Amsterdam (1971), 376-381.Google Scholar
- 18 Tarjan, R.E. Solving path problems on directed graphs. Tech. Rep. STAN-CS-75-528, Comptr. Sci. Dept., Stanford U., Stanford, Calif., Nov. 1975. Google ScholarDigital Library
Index Terms
- A practical interprocedural data flow analysis algorithm
Recommendations
An interprocedural data flow analysis algorithm
POPL '77: Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languagesA new interprocedural data flow analysis algorithm is presented and analyzed. The algorithm associates with each procedure in a program information about which variables may be modified, which may be used, and which are possibly preserved by a call on ...
Double iterative framework for flow-sensitive interprocedural data flow analysis
Compiler optimization, parallel processing, data flow testing, and symbolic debugging can benefit from interprocedural data flow analysis. However, the live, reaching definition, and most summary data flow problems are theoretically intractable in the ...
A practical framework for demand-driven interprocedural data flow analysis
The high cost and growing importance of interprocedural data flow analysis have led to an increased interest in demand-driven algorithms. In this article, we present a general framework for developing demand-driven interprocedural data flow analyzers ...
Comments