High-level data flow analysis

ABSTRACT

In contrast to the predominant use of low-level intermediate text, high-level data flow analysis deals with programs essentially at source level and exploits the control flow information implicit in the parse tree. The need for high-level flow analysis arises from several aspects of recent work on advanced methods of program certification and optimization. This paper proposes a simple general method of high-level data flow analysis that allows free use of escape and jump statements, avoids large graphs when compiling large programs, facilitates updating of data flow information to reflect program changes, and derives new global information helpful in solving many familiar global flow analysis problems. An illustrative application to live variable analysis is presented. Many of the graphs involved are constructed and analyzed before any programs are compiled, thus avoiding certain costs that low-level methods incur repeatedly at compile time.

REFERENCES

• 1: Allen, F.E. Program optimization.Ann. Rev. in Autom. Prog. 5 (1969), 239-307.
• 2: Allen, F.E. Interprocedural data flow analysis. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 398- 402.
• 3: Backus, J.W., et al. The FORTRAN automatic coding system. Proc. Western Joint Comptr. Conf., Feb. 1957, pp. 188-198.
• 4: Vincent A. Busam , Donald E. Englund, Optimization of expressions in Fortran, Communications of the ACM, v.12 n.12, p.666-674, Dec. 1969 [doi>10.1145/363626.363635]
• 5: John Cocke, Global common subexpression elimination, Proceedings of a symposium on Compiler optimization, p.20-24, July 27-28, 1970, Urbana-Champaign, Illinois
• 6: Ole Johan Dahl, Structured Programming, Academic Press, Inc., Orlando, FL, 1972
• 7: Fosdick, L.D., and Osterweil, L.J. Data flow analysis in software reliability. Rep. CU-CS-087-76, Comptr. Sci. Dept., Colorado U., Boulder, Colo., May 1976.
• 8: Daniel P. Friedman , Stuart C. Shapiro, A case for while-until, ACM SIGPLAN Notices, v.9 n.7, p.7-14, July 1974 [doi>10.1145/953224.953225]
• 9: Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
• 10: Hecht, M.S., and Schaffer, J.B. Ideas on the design of a quad improver for SIMPL-T, Pt. I. Tech. Rep. TR-405, Comptr. Sci. Dept., U. of Maryland, College Park, Md., Aug. 1975.
• 11: Hecht, M.S., and Ullman, J.D. A simple algorithm for global data flow analysis problems. SIAM J. Comptng. 4 (1975), 519-532.
• 12: John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
• 13: Lawrence T. Kou, On Live-Dead Analysis for Global Data Flow Problems, Journal of the ACM (JACM), v.24 n.3, p.473-483, July 1977 [doi>10.1145/322017.322027]
• 14: Kennedy, K. A global flow analysis algorithm. Int. J. Comptr. Math. (A) 3 (1971), 5-15.
• 15: K. W. Kennedy, Node listings applied to data flow analysis, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.10-21, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512978]
• 16: Ken Kennedy , Scott K. Warren, Automatic generation of efficient evaluators for attribute grammars, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.32-49, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811538]
• 17: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 18: Donald E. Knuth, Structured Programming with go to Statements, ACM Computing Surveys (CSUR), v.6 n.4, p.261-301, Dec. 1974 [doi>10.1145/356635.356640]
• 19: Knuth, D.E., and Zahn, C.T. Ill-chosen use of "event". Comm. ACM 18, 6 (June 1975), 360.
• 20: David B. Loveman, Program improvement by source to source transformation, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.140-152, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811548]
• 21: Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
• 22: A. Maggiolo-Schettini , B. K. Rosen , H. R. Strong, Procedure linkage optimization working paper, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.183-193, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512944]
• 23: Osterweil, L.J., and Fosdick, L.D. Data flow analysis as an aid in documentation, assertion generation, validation, and error detection. Rep. CU-CS-055-74, Comptr. Sci. Dept., Colorado U., Boulder, Colo., Sept. 1974.
• 24: Rosen, B.K. Correctness of parallel programs: the Church- Rosser approach. Theoretical Comptr. Sci. 2 (1976), 183-207.
• 25: Barry K. Rosen, Data Flow Analysis for Procedural Languages, Journal of the ACM (JACM), v.26 n.2, p.322-344, April 1979 [doi>10.1145/322123.322135]
• 26: Marvin Schaefer, A mathematical theory of global program optimization (Prentice-Hall series in automatic computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1973
• 27: Schneck, P.B., and Angel, E. A FORTRAN to FORTRAN optimising compiler. Computer J. 16 (1973), 322-330.
• 28: Richard Lee Sites, Proving that computer programs terminate cleanly., 1974
• 29: Spillman, T.C. Exposing side effects in a PL/I optimizing compiler. Information Processing 71, North Holland Pub. CO., Amsterdam, 1971, pp. 378-381.
• 30: Tarjan, R. Depth-first search and linear graph algorithms. SIAM J. Comptng. 1 (1972), 146-160.
• 31: Ullman, J.D. Data flow analysis. Second USA-Japan Comptr. Conf., 1975, pp. 335-342.
• 32: Wegbreit, B. Property extraction in well-founded property sets. IEEE Trans. on Software Engineering SE-1 (1975), 270-285.
• 33: William Allan Wulf , Richard K. Johnsson , Charles B. Weinstock , Steven O. Hobbs , Charles M. Geschke, The Design of an Optimizing Compiler, Elsevier Science Inc., New York, NY, 1975
• 34: Charles T. Zahn, Jr., A control statement for natural top-down structured programming, Programming Symposium, Proceedings Colloque sur la Programmation, p.170-180, April 09-11, 1974
• 35: Zelkowitz, M.V., and Bail, W.G. Optimization of structured programs. Software Practice and Experience 4 (1974), 51-57.

INDEX TERMS

Keywords:
control flow graph, data flow analysis, escapes, exits, goto statements, high-level language, jumps, structured programming