Flow analysis and optimization of LISP-like structures

ABSTRACT

In [12] the authors introduced the concept of binding time optimization and presented a series of data flow analytic methods for determining some of the binding time characteristics of programs. In this paper we extend that work by providing methods for determining the class of shapes which an unbounded data object may assume during execution of a LISP-like program, and describe a number of uses to which that information may be put to improve storage allocation in compilers and interpreters for advanced programming languages.We are concerned chiefly with finding, for each program point and variable a finite description of a set of graphs which includes all the shapes of values the variable could assume at that point during the execution of a program. If this set is small or regular in structure, this information can be used to optimize the program's execution, mainly by use of more efficient storage allocation schemes.In the first part we show how to construct from a program without selective updating a tree grammar whose nonterminals generate the desired sets of graphs; in this case they will all be trees. The tree grammars are of a more general form than is usually studied [8, 19], so we show that they may be converted to the usual form. The resulting tree grammar could naturally be viewed as a recursive type definition [11] of the values the variables may assume. Further, standard algorithms may be employed to test for infiniteness, emptiness or linearity of the tree structure.In the second part selective updating is allowed, so an alternate semantics is introduced which more closely resembles traditional LISP implementations, and which is equivalent to the tree model for programs without selective updating. In this model data objects are directed graphs. We devise a finite approximation method which provides enough information to detect cell sharing and cyclic structures whenever they can possibly occur. This information can be used to recognize when the use of garbage collection or of reference counts may be avoided.The work reported in the second part of this paper extends that of Schwartz [17] and Cousot and Cousot [7]. They have developed methods for determining whether the values of two or more variables share cells, while we provide information on the detailed structure of what is shared. The ability to detect cycles is also new. It also extends the work of Kaplan [13], who distinguishes only binary relations among the variables of a program, does not handle cycles, and does not distinguish selectors (so that his analysis applies to nodes representing sets rather than ordered tuples).

REFERENCES

• 1: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 2: Jeffrey M. Barth, Shifting garbage collection overhead to compile time, Communications of the ACM, v.20 n.7, p.513-518, July 1977 [doi>10.1145/359636.359713]
• 3: Brainerd, W. S., Tree Generating Regular Systems, Information and Control, vol. 14, 1969, pp. 217 - 231.
• 4: Büchi, J. R., Regular Canonical Systems, Archiv f. Math. Logik und Grund., vol. 6, 1964, pp. 91 - 111.
• 5: Douglas W. Clark , C. Cordell Green, An empirical study of list structure in Lisp, Communications of the ACM, v.20 n.2, p.78-87, Feb. 1977 [doi>10.1145/359423.359427]
• 6: Patrick Cousot , Radhia Cousot, Automatic synthesis of optimal invariant assertions: Mathematical foundations, Proceedings of the 1977 symposium on Artificial intelligence and programming languages, p.1-12, August 15-17, 1977
• 7: Patrick Causot , Radhia Cousot, Static determination of dynamic properties of generalized type unions, ACM SIGPLAN Notices, v.12 n.3, p.77-94, March 1977
• 8: Engelfriet, J., Tree Automata and Tree Grammars, DAIMI Report FN-10, Department of Computer Science, University of Aarhus, Denmark, 1975.
• 9: Seymour Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, Inc., New York, NY, 1966
• 10: Goto, E., Monocopy and Associative Algorithms in an Extended LISP, University of Tokyo, Japan, May 1974.
• 11: Hoare, C. A. R., Recursive Data Structures, Inter. J. Comp. and Sys. Sci., vol. 4, no. 2, 1975, pp. 105 - 132.
• 12: Neil D. Jones , Steven S. Muchnick, Binding time optimization in programming languages: Some thoughts toward the design of an ideal language, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.77-94, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811542]
• 13: Kaplan, Marc, Relational Data Flow Analysis, Technical Report 243, Dept. of Elec. Eng. and Comp. Sci., Princeton University, April 1978 (revised).
• 14: Marc A. Kaplan , Jeffrey D. Ullman, A general scheme for the automatic inference of variable types, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.60-75, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512768]
• 15: Robert Milne , C. Strachey, A Theory of Programming Language Semantics, Halsted Press, New York, NY, 1977
• 16: Reynolds, John C., Automatic Computation of Data Set Definitions, Proc. of IFIP Congress 68, August 1968, pp. B69 - B73.
• 17: Schwartz, J. T., Optimization of Very High Level Languages - I: Value Transmission and Its Corollaries, Computer Languages, vol. 1, 1975, pp. 161 - 194.
• 18: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 19: Thatcher, J., Tree Automata: An Informal Survey, in Aho, Alfred (ed.), Currents in the Theory of Computing, Prentice-Hall, 1973, pp. 143 - 172.