Applications of a graph grammar for program control flow analysis

ABSTRACT

A standard approach to the analysis of program structure for the purpose of code optimization is to construct the "control flow graph" which models the possible execution paths through the program. Various graph algorithms can be applied to the control flow graph to produce data flow information, possible optimizations, etc. [A1,A2,AC,AU2,AU3,CS,HU1,HU2.HU3,Ke1,Ke2,Ke3,Ke4,Sc,U]. Studies of the form of typical control flow graphs indicate that such graphs tend to fall into a restricted subclass of general graphs. For example, empirical investigations have shown that the vast majority of program graphs have no multiple-entry loops [AC,HU2,HU3,Kn1].The recent work on "structured programming" has suggested that "good" programs fall into an even more restricted subclass. In fact, purists recommend that all programs be synthesized from three basic control structures: sequential statements, if-then-else statements, and single-entry single-exit loops [Di,Wi].Formal language theory [HoU] has given us a practical way to specify the set of strings which comprise a given language: via a grammar. It is then a natural idea to extend grammars from the strings to graphs in hopes of getting the same power of expression. Several researchers have used this approach [FKZ,J2,Ro].In this paper we study the applicability of a grammatical approach to describing the set of control flow graphs which arise from "good" programs in the sense proposed by many programming practitioners. The resulting flow graph language contains all those programs constructed according to the purists' rules and also admits programs with multiple-exit loops if such loops are constructed sensibly. The grammar we use is the "semi-structured flow graph" grammar GSSFG which was studied originally in [FKZ]. There are several appealing properties of this grammar; perhaps the most important, from the point-of-view of a compiler-writer, is the existence of a linear-time parsing algorithm which leads directly to a linear-time data flow analysis method [FKZ].In the present work we summarize the results from [FKZ] and address several new questions. First, how often do programs written by people with no knowledge of the SSFG rules fall into the language defined by GSSFG? In other words, is the language a natural one for programming? Second, once a program has been parsed according to GSSFG do benefits other than fast data flow analysis accrue?The paper is organized into three main sections. Section II introduces GSSFG and the parsing algorithm from [FKZ]. Section III is devoted to an empirical study conducted by the authors in an attempt to answer the question of naturalness, described above. Section IV discusses several applications of the graph parse in a "graph attribute grammar" framework. The summary at the end of the paper includes suggestions for further investigation.

REFERENCES

• 1: {ASU} Aho, A. V., Sethi, R. and Ullmann, J. D., "Code Optimization and Finite Church-Rosser Systems" in Design and Optimization of Compilers, (R. Rustin, ed.) Prentice-Hall, Englewood Cliffs, N.J., 1972.
• 2: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 3: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 4: A. V. Aho , J. D. Ullman, Node listings for reducible flow graphs, Proceedings of seventh annual ACM symposium on Theory of computing, p.177-185, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803767]
• 5: Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
• 6: {A2} Allen, F. E., "A Basis for Program Optimization," Proc. IFIP Conf. 71, North-Holland Publishing Co. Amsterdam, 1971.
• 7: {AC} Allen, F. E. and Cocke, J., "Graph Theoretic Constructs for Program Flow Analysis," IBM Research Report RC 3923, T.J. Watson Research Center, Yorktown Heights, N.Y., July 1972.
• 8: {AM} Ashcroft, E. and Manna, Z., "The Translation of 'Goto' Programs Into 'While' Programs," Proc. IFIP Conf. 71, North Holland Publishing Co., Amsterdam, 1971.
• 9: {Be} Beatty, J. C., "An Algorithm for Tracing Live Variables Based On A Straightened Program Graph," IBM Technical Report TR 00.2503, IBM Poughkeepsie Laboratory, December 1973.
• 10: Corrado Böhm , Giuseppe Jacopini, Flow diagrams, turing machines and languages with only two formation rules, Communications of the ACM, v.9 n.5, p.366-371, May 1966 [doi>10.1145/355592.365646]
• 11: {CK} Cocke, J. and Kennedy, K., "Profitability Computations on Program Flow Graphs," IBM Research Report RC 5123, T.J. Watson Research Center, Yorktown Heights, N.Y., November 1974.
• 12: John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
• 13: {Di} Dijkstra, E. W., "Notes on Structured Programming," in Dahl, Dijkstra and Hoare, Structured Programming, Academic Press (1972).
• 14: C. P. Earnest , K. G. Balke , J. Anderson, Analysis of Graphs by Ordering of Nodes, Journal of the ACM (JACM), v.19 n.1, p.23-42, Jan. 1972 [doi>10.1145/321679.321683]
• 15: {FKZ} Farrow, R., Kennedy, K., and Zucconi, L., "Graph Grammars and Global Program Data Flow Analysis," to appear in Proceedings of the Seventeenth Annual IEEE Symposium on the Foundations of Computer Science, October 1976.
• 16: 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]
• 17: Susan L. Graham , Mark Wegman, A fast and usually linear algorithm for global flow analysis, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.22-34, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512979]
• 18: Matthew S. Hecht , Jeffrey D. Ullman, Analysis of a simple algorithm global data flow problems, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.207-217, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512946]
• 19: {HU2} Hecht, M. S., and Ullman, J. D., "Flow Graph Reducibility," SIAM J. Computing, Vol. 1, No. 2, pp. 188-202, June 1972.
• 20: M. S. Hecht , J. D. Ullman, Characterizations of Reducible Flow Graphs, Journal of the ACM (JACM), v.21 n.3, p.367-375, July 1974 [doi>10.1145/321832.321835]
• 21: Mehdi Jazayeri, On attribute grammars and the semantic specification of programming languages., 1975
• 22: {J2} Jazayeri, M., "Live Variable Analysis, Attribute Grammars, and Program Optimization," draft, Dept. of Computer Science, University of North Carolina, Chapel Hill, N.C. March 1975.
• 23: Richard H. Karpinski, An unstructured view of structured programming, ACM SIGPLAN Notices, v.9 n.3, March 1974 [doi>10.1145/987419.987422]
• 24: {Ke1} Kennedy, K., "A Global Flow Analysis Algorithm," International J. Computer Math., Section A, Vol. 3, pp. 5-15, Dec. 1971.
• 25: {Ke2} Kennedy, K., "A Comparison of Algorithms for Global Flow Analysis," Technical Report 476-093-1, Dept. of Mathematical Sciences, Rice University, Houston, Texas, Feb. 1974.
• 26: 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]
• 27: {Ke4} Kennedy, K., "Use-definition Chains with Applications," Rice Technical Report 476-093-9, Dept. of Mathematical Sciences, Rice University, Houston, Texas, April 1975.
• 28: {KR} Kennedy, K. and Ramanathan, J., "A Deterministic Attribute Grammar Evaluator Based on Dynamic Sequencing," Technical Report 476-093-12, Dept. of Mathematical Sciences, Rice University, Houston, Texas, Oct. 1975.
• 29: 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]
• 30: Brian W. Kernighan , P. J. Plauger, The Elements of Programming Style, McGraw-Hill, Inc., New York, NY, 1982
• 31: Brian W. Kernighan , P. J. Plauger, Programming Style: Examples and Counterexamples, ACM Computing Surveys (CSUR), v.6 n.4, p.303-319, Dec. 1974 [doi>10.1145/356635.356641]
• 32: 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]
• 33: {Kn1} Knuth, Donald E., "An Empirical Study of Fortran Programs," Software Practice and Experience, Vol. 1, No. 2, 1971, pp. 105-134.
• 34: 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]
• 35: {Kn3} Knuth, Donald E., "Semantics of Context-Free Languages," Math. Systems Theory J. 2, pp. 127-145 (1968).
• 36: {Kn4} Knuth, Donald E., "Semantics of Context-Free Languages: Correction," Math Systems Theory J 5, p. 95 (1971).
• 37: R. C. T. Lee , S. K. Chang, Structured programming and automatic program synthesis, ACM SIGPLAN Notices, v.9 n.4, p.60-70, April 1974
• 38: {MT} Markowsky, G. and Tarjan, R. E., "Lower Bounds on the Lengths of Node Sequences in Directed Graphs," IBM Research Report RC 5477, T.J. Watson Research Center, Yorktown Heights, N.Y., July 1975.
• 39: Johannes J. Martin, The 'natural' set of basic control structures, ACM SIGPLAN Notices, v.8 n.12, December 1973 [doi>10.1145/987006.987008]
• 40: Barry K. Rosen, Tree-Manipulating Systems and Church-Rosser Theorems, Journal of the ACM (JACM), v.20 n.1, p.160-187, Jan. 1973 [doi>10.1145/321738.321750]
• 41: Stuart H. Sanfield, The scope of variable concept: the key to structured programming?, ACM SIGPLAN Notices, v.9 n.7, p.22-29, July 1974 [doi>10.1145/953224.953227]
• 42: Marvin Schaefer, A mathematical theory of global program optimization (Prentice-Hall series in automatic computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1973
• 43: Ravi Sethi, Testing for the Church-Rosser Property, Journal of the ACM (JACM), v.21 n.4, p.671-679, Oct. 1974 [doi>10.1145/321850.321862]
• 44: Ben Shneiderman, The chemistry of control structures, ACM SIGPLAN Notices, v.9 n.12, p.29-34, December 1974 [doi>10.1145/953246.953249]
• 45: {T} Tarjan, R. E., "Depth-First Search and Linear Graph Algorithms," SIAM J. Computing, Vol. 1, No. 2, June 1972.
• 46: {U} Ullman, J. D., "Fast Algorithms for the Elimination of Common Subexpressions," Acta Informatica, Vol. 2, pp. 191-213, 1973.
• 47: Eberhard Wegner, Control constructs for programming languages, ACM SIGPLAN Notices, v.10 n.2, p.34-41, February 1975 [doi>10.1145/953438.953443]
• 48: N. H. Weiderman , B. M. Rawson, Flowcharting loops without cycles, ACM SIGPLAN Notices, v.10 n.4, April 1975 [doi>10.1145/987278.987283]
• 49: Niklaus Wirth, On the Composition of Well-Structured Programs, ACM Computing Surveys (CSUR), v.6 n.4, p.247-259, Dec. 1974 [doi>10.1145/356635.356639]
• 50: W. A. Wulf , D. B. Russell , A. N. Habermann, BLISS: a language for systems programming, Communications of the ACM, v.14 n.12, p.780-790, Dec. 1971 [doi>10.1145/362919.362936]
• 51: {Z} Zahn, C. T., "Structured Control in Programming Languages," Proceedings of the 1975 NCC, AFIPS Conference Proceedings, Vol. 44, AFIPS Press (1975).