Qualified data flow problems

ABSTRACT

It is known that not all paths are possible in the run time control flow of many programs. It is also known that data flow analysis cannot restrict attention to exactly those paths that are possible. It is therefore usual for analytic methods to consider all paths. Sharper information can be obtained by considering a recursive set of paths that is large enough to include all possible paths but small enough to exclude many of the impossible ones. This paper presents a simple uniform methodology for sharpening data flow information by considering certain recursive path sets of practical importance. Associated with each control flow arc there is a relation on a finite set Q. The paths that qualify to be considered are (essentially) those for which the composition of the relations encountered is nonempty. For example, Q might be the set of all assignments of values to each of several bit variables used by a program to remember some facts about the past and branch accordingly in the future. Given any data flow problem together with qualifying relations on Q associated with the control flow arcs, we construct a new problem. Considering all paths in the new problem is equivalent to considering only qualifying paths in the old one. Preliminary experiments (with a small set of real programs) indicate that qualified analysis is feasible and substantially more informative than ordinary analysis. The methodology also has a beneficial feedback effect on the delicate task of passing from programs to meaningful data flow analysis problems. Even when all paths qualify, unusually sharp information can be obtained by passing from programs to problems in ways suggested by our theorems.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: F. E. Allen , J. Cocke, A program data flow analysis procedure, Communications of the ACM, v.19 n.3, p.137, March 1976 [doi>10.1145/360018.360025]
• 3: BJ78. Babich, W. A., and Jazayeri, M. The method of attributes for data flow analysis (Part II. Demand analysis). Acts Informatica10 (1978), 265-272.
• 4: 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]
• 5: Ha77. Harrison, W. H. Compiler analysis of the value ranges for variables. IEEE Trans. on Software Engineering3 (1977), 243-250.
• 6: HU75. Hecht, M. S., and Ullman, J. D. A simple algorithm for global data flow analysis problems. SIAM J. Computing4 (1975), 519-532.
• 7: JM80. Jones, N. D., and Muchnick, S. S. (Eds.) Program Flow Analysis: Theory and Applications. Prentice-Hall, Englewood Cliffs NJ, 1980(?), to appear.
• 8: 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]
• 9: Ken Kennedy , Linda Zucconi, Applications of a graph grammar for program control flow analysis, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.72-85, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512958]
• 10: 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]
• 11: Kn71. Knuth, D. E. An empirical study of FORTRAN programs. Software Practice and Experience1 (1971), 105-134.
• 12: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• 13: Barry K. Rosen, Monoids for rapid data flow analysis, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.47-59, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512767]
• 14: Ro80a. Rosen, B. K. Monoids for rapid data flow analysis. SIAM J. Computing9 (1980), to appear. (An earlier version with different numbering appears as {Ro78}.)
• 15: Ro80b. Rosen, B. K. Degrees of availability as an introduction to the general theory of data flow analysis. (To appear in {JM80}.)
• 16: SP78. Sharir, M., and Pnueli, A. Two approaches to interprocedural data flow analysis. Report 002, Computer Science Department, New York University, New York, September 1978. (Revision to appear in {JM80}.)
• 17: Michel Sintzoff, Calculating properties of programs by valuations on specific models, Proceedings of ACM conference on Proving assertions about programs, p.203-207, January 06-07, 1972, Las Cruces, New Mexico, United States
• 18: Robert E Tarjan, Solving path problems on directed graphs., Stanford University, Stanford, CA, 1975
• 19: Ul73. Ullman, J. D. Fast algorithms for the elimination of common subexpressions. Acta Informatica2 (1973), 191-213.
• 20: We75. Wegbreit, B. Property extraction in well-founded property sets. IEEE Trans. on Software Engineering1 (1975), 270-285.